結果
問題 | No.937 Ultra Sword |
ユーザー |
|
提出日時 | 2019-11-29 22:51:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 3,000 ms |
コード長 | 891 bytes |
コンパイル時間 | 612 ms |
コンパイル使用メモリ | 69,628 KB |
実行使用メモリ | 18,052 KB |
最終ジャッジ日時 | 2024-11-21 02:40:15 |
合計ジャッジ時間 | 6,789 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 9 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> using namespace std; int N,A[1<<17]; long S[1<<17]; long sum=0,ans=0; long B[1700000]; bool dp[1<<17]; main() { cin>>N; int sz=0; for(int i=0;i<N;i++) { long a;cin>>a;A[a]++; sum+=a; for(int j=0;j<17;j++) { B[i*17+j]=a<<j; } } for(int i=100000;i>1;i--) { for(int j=i;j<=100000;j+=i) { S[i]+=A[j]*(long)(j/i*(i-1)); } } int idx=0; for(int i=33;i>=0;i--) { int id=-1; for(int j=idx;j<17*N;j++) { if(B[j]>>i&1) { id=j; break; } } if(id<0)continue; if(id!=idx) { swap(B[id],B[idx]); } for(int j=0;j<17*N;j++) { if(idx!=j&&B[j]>>i&1)B[j]^=B[idx]; } idx++; } dp[0]=true; for(int i=0;i<17*N;i++) { if(B[i]&&!(B[i]>>17)) { for(int k=0;k<1<<17;k++) { if(dp[k])dp[k^B[i]]=true; } } } for(int i=0;i<1<<17;i++)if(dp[i])ans=max(ans,S[i]); cout<<sum-ans<<endl; }