Submission #3001121


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=105;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

int N;
int a[maxn];

struct edge{
	int to,cap,rev;
	edge(int _,int __,int ___):to(_),cap(__),rev(___){}
};

vector<edge> G[maxn];

void add_edge(int u,int v,int c){
	//cout<<u<<' '<<v<<' '<<c<<'\n';
	G[u].pb(edge(v,c,SZ(G[v])));
	G[v].pb(edge(u,0,SZ(G[u])-1));
}

int lvl[maxn];
int iter[maxn];

vector<int> q;
int pt;
void bfs(int u){
	REP(i,N) lvl[i]=-1;
	lvl[u]=0;
	q.clear();
	q.pb(u);
	pt=0;
	while(pt<SZ(q)){
		int cur=q[pt++];
		for(edge &e:G[cur]){
			if(lvl[e.to]!=-1||e.cap<=0) continue;
			lvl[e.to]=lvl[cur]+1;
			q.pb(e.to);
		}
	}
}
int dfs(int s,int t,int f){
	if(s==t) return f;
	for(int &i=iter[s];i<SZ(G[s]);i++){
		edge &e=G[s][i];
		if(e.cap>0&&lvl[e.to]>lvl[s]){
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
}

int dinic(int s,int t){
	int flow=0;
	while(1){
		bfs(s);
		REP(i,N) iter[i]=0;
		if(lvl[t]==-1) return flow;
		int f;
		while((f=dfs(s,t,INF))>0) flow+=f;
	}
}

int main()
{
	int n;
	cin>>n;
	N=n+2;
	REP(i,n) cin>>a[i];
	int ans=0;
	REP(i,n) ans+=max(a[i],0);
	REP(i,n){
		if(a[i]<0) add_edge(n,i,-a[i]);
		if(a[i]>0) add_edge(i,n+1,a[i]);
	}
	for(int i=1;i<=n;i++) for(int j=2*i;j<=n;j+=i){
		add_edge(i-1,j-1,INF);
	}
	cout<<ans-dinic(n,n+1);
}


Submission Info

Submission Time
Task E - MUL
User iloveUtaha
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2724 Byte
Status TLE
Exec Time 2103 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
TLE × 2
AC × 3
TLE × 46
Set Name Test Cases
Sample example_0, example_1, example_2, example_3
All example_0, example_1, example_2, example_3, kimeuti_0, kimeuti_1, kimeuti_10, kimeuti_11, kimeuti_12, kimeuti_13, kimeuti_14, kimeuti_15, kimeuti_16, kimeuti_17, kimeuti_18, kimeuti_19, kimeuti_2, kimeuti_3, kimeuti_4, kimeuti_5, kimeuti_6, kimeuti_7, kimeuti_8, kimeuti_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_2, small_3, small_4
Case Name Status Exec Time Memory
example_0 TLE 2103 ms 256 KB
example_1 AC 1 ms 256 KB
example_2 AC 1 ms 256 KB
example_3 TLE 2103 ms 256 KB
kimeuti_0 TLE 2103 ms 256 KB
kimeuti_1 TLE 2103 ms 256 KB
kimeuti_10 TLE 2103 ms 256 KB
kimeuti_11 TLE 2103 ms 256 KB
kimeuti_12 TLE 2103 ms 256 KB
kimeuti_13 TLE 2103 ms 256 KB
kimeuti_14 TLE 2103 ms 256 KB
kimeuti_15 TLE 2103 ms 256 KB
kimeuti_16 TLE 2103 ms 256 KB
kimeuti_17 TLE 2103 ms 256 KB
kimeuti_18 TLE 2103 ms 256 KB
kimeuti_19 TLE 2103 ms 256 KB
kimeuti_2 TLE 2103 ms 256 KB
kimeuti_3 TLE 2103 ms 256 KB
kimeuti_4 TLE 2103 ms 256 KB
kimeuti_5 TLE 2103 ms 256 KB
kimeuti_6 TLE 2103 ms 256 KB
kimeuti_7 TLE 2103 ms 256 KB
kimeuti_8 TLE 2103 ms 256 KB
kimeuti_9 TLE 2103 ms 256 KB
rand_0 TLE 2103 ms 256 KB
rand_1 TLE 2103 ms 256 KB
rand_10 TLE 2103 ms 256 KB
rand_11 TLE 2103 ms 256 KB
rand_12 TLE 2103 ms 256 KB
rand_13 TLE 2103 ms 256 KB
rand_14 TLE 2103 ms 256 KB
rand_15 TLE 2103 ms 256 KB
rand_16 TLE 2103 ms 256 KB
rand_17 TLE 2103 ms 256 KB
rand_18 TLE 2103 ms 256 KB
rand_19 TLE 2103 ms 256 KB
rand_2 TLE 2103 ms 256 KB
rand_3 TLE 2103 ms 256 KB
rand_4 TLE 2103 ms 256 KB
rand_5 TLE 2103 ms 256 KB
rand_6 TLE 2103 ms 256 KB
rand_7 TLE 2103 ms 256 KB
rand_8 TLE 2103 ms 256 KB
rand_9 TLE 2103 ms 256 KB
small_0 TLE 2103 ms 256 KB
small_1 TLE 2103 ms 256 KB
small_2 AC 1 ms 256 KB
small_3 TLE 2103 ms 256 KB
small_4 TLE 2103 ms 256 KB