Submission #3978398
Source Code Expand
# include "iostream"
# include "cstdio"
# include "queue"
using namespace std;
const int maxm=1e5+10;
const long long Inf=1ll<<50;
int head[maxm],tot=1,N,Cnt,S,T;
int Deep[maxm];
long long A[maxm];
struct edge{
int To;
int Next;
long long Value;
# define To(x) Edge[x].To
# define Next(x) Edge[x].Next
# define Value(x) Edge[x].Value
}Edge[maxm<<1];
inline void Add_Edge(int From,int To,long long Value){Edge[++tot]=(edge){To,head[From],Value},head[From]=tot;return;}
inline void Insert_Edge(int From,int To,long long Value){Add_Edge(From,To,Value);Add_Edge(To,From,0);return;}
inline bool Bfs(int S,int T){
register int i,x;
for(i=1;i<=N+2;i++) Deep[i]=0;
queue<int> q;
q.push(S);
Deep[S]=1;
while(q.size()){
x=q.front(),q.pop();
for(i=head[x];i;i=Next(i)){
if(Value(i) && !Deep[To(i)]){
q.push(To(i));
Deep[To(i)]=Deep[x]+1;
if(To(i)==T) return true;
}
}
}
return false;
}
long long Dfs(int now,long long Now){
if(now==T) return Now;
long long Rest=Now,Reduce;
for(int i=head[now];i && Rest;i=Next(i)){
if(Value(i) && Deep[To(i)]==Deep[now]+1){
Reduce=Dfs(To(i),min(Rest,Value(i)));
if(!Reduce) Deep[To(i)]=0;
Value(i)-=Reduce;
Value(i^1)+=Reduce;
Rest-=Reduce;
}
}
return Now-Rest;
}
int main(){
register int i,j;
register long long Ans=0,Now,Max=0;
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%lld",A+i);
S=N+1;
T=N+2;
for(i=1;i<=N;i++){
if(A[i]>0){
Insert_Edge(S,i,A[i]);
Ans+=A[i];
}else{
Insert_Edge(i,T,-A[i]);
}
}
for(i=1;i<=N;i++){
for(j=i<<1;j<=N;j+=i){
Insert_Edge(j,i,Inf);
}
}
while(Bfs(S,T)){
while(Now=Dfs(S,Inf)){
Max+=Now;
}
}
cout<<Ans-Max<<endl;
return 0;
}
Submission Info
Submission Time
2019-01-11 23:55:18+0900
Task
E - MUL
User
July
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
1941 Byte
Status
AC
Exec Time
3 ms
Memory
2304 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:63:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
./Main.cpp:64:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=N;i++) scanf("%lld",A+i);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
700 / 700
Status
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
AC
2 ms
2304 KB
example_1
AC
3 ms
2304 KB
example_2
AC
2 ms
2304 KB
example_3
AC
2 ms
2304 KB
kimeuti_0
AC
2 ms
2304 KB
kimeuti_1
AC
2 ms
2304 KB
kimeuti_10
AC
2 ms
2304 KB
kimeuti_11
AC
2 ms
2304 KB
kimeuti_12
AC
2 ms
2304 KB
kimeuti_13
AC
2 ms
2304 KB
kimeuti_14
AC
2 ms
2304 KB
kimeuti_15
AC
2 ms
2304 KB
kimeuti_16
AC
2 ms
2304 KB
kimeuti_17
AC
2 ms
2304 KB
kimeuti_18
AC
2 ms
2304 KB
kimeuti_19
AC
2 ms
2304 KB
kimeuti_2
AC
2 ms
2304 KB
kimeuti_3
AC
2 ms
2304 KB
kimeuti_4
AC
2 ms
2304 KB
kimeuti_5
AC
2 ms
2304 KB
kimeuti_6
AC
2 ms
2304 KB
kimeuti_7
AC
2 ms
2304 KB
kimeuti_8
AC
2 ms
2304 KB
kimeuti_9
AC
2 ms
2304 KB
rand_0
AC
2 ms
2304 KB
rand_1
AC
2 ms
2304 KB
rand_10
AC
2 ms
2304 KB
rand_11
AC
2 ms
2304 KB
rand_12
AC
2 ms
2304 KB
rand_13
AC
2 ms
2304 KB
rand_14
AC
2 ms
2304 KB
rand_15
AC
2 ms
2304 KB
rand_16
AC
2 ms
2304 KB
rand_17
AC
2 ms
2304 KB
rand_18
AC
2 ms
2304 KB
rand_19
AC
2 ms
2304 KB
rand_2
AC
2 ms
2304 KB
rand_3
AC
2 ms
2304 KB
rand_4
AC
2 ms
2304 KB
rand_5
AC
2 ms
2304 KB
rand_6
AC
2 ms
2304 KB
rand_7
AC
2 ms
2304 KB
rand_8
AC
2 ms
2304 KB
rand_9
AC
2 ms
2304 KB
small_0
AC
2 ms
2304 KB
small_1
AC
2 ms
2304 KB
small_2
AC
2 ms
2304 KB
small_3
AC
2 ms
2304 KB
small_4
AC
2 ms
2304 KB