QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87823 | #21. GCD-sum | SenseAnone | 5 | 2ms | 3804kb | C++14 | 2.9kb | 2023-03-14 14:18:58 | 2023-03-14 14:18:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int n;
ll arr[500005];
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
namespace Subtask1{
int dp[32780][16];
inline int Calc(int S)
{
int Val=0;
for(int i=1;i<=n;i++) if((S>>(i-1))&1) Val=gcd(Val,arr[i]);
return Val;
}
void Main()
{
for(int i=1;i<=n;i++) read(arr[i]);
for(int i=0;i<(1<<n);i++) for(int j=0;j<=n;j++) dp[i][j]=-1e9;
dp[0][0]=0;
for(int S=1;S<(1<<n);S++)
{
for(int i=1;i<=n;i++)
{
for(int T=S;T;T=(T-1)&S)
{
if(dp[S^T][i-1]!=-1e9)
{
int res=dp[S^T][i-1]+Calc(T);
dp[S][i]=max(dp[S][i],res);
}
}
}
}
int U=(1<<n)-1;
for(int i=1;i<=n;i++) printf("%d\n",dp[U][i]);
exit(0);
}
}
namespace SubtaskDaoLi{
bool vis[2005];
ll Pre[10005],Suf[10005];
vector <ll> V;
void Main()
{
ll All=0;
for(ll i=1;i<=n;i++) read(arr[i]),V.push_back(arr[i]),All=gcd(All,arr[i]);
printf("%lld\n",All); sort(V.begin(),V.end());
ll Now=All,pos=0,Oth=0;
for(ll i=2;i<=n;i++)
{
for(ll j=0;j<(ll)V.size();j++) Pre[j]=gcd(Pre[j-1],vis[V[j]]?0:V[j]);
Suf[V.size()]=0;
for(ll j=V.size()-1;j>=0;j--) Suf[j]=gcd(Suf[j+1],vis[V[j]]?0:V[j]);
ll lst=-1;
for(ll j=V.size()-1;j>V.size()-4&&j>=0;j++)
{
ll k=j+1;
while(k<V.size()&&vis[V[k]]) k++;
if(gcd(lst==-1?0:Pre[lst],k==V.size()?0:Suf[k])+V[j]+Oth>Now) Now=gcd(Pre[lst],Suf[k])+V[j]+Oth,pos=j;
if(j!=(ll)V.size()-1&&V[j]!=V[j+1]&&!vis[V[j]]) lst=j;
j=k-1;
}
printf("%lld\n",Now); vis[V[pos]]=true; Oth+=V[pos];
if(i!=n) V.erase(V.begin()+pos);
}
}
}
int main() {
// freopen("divide.in","r",stdin);
// freopen("divide.out","w",stdout);
read(n);
if(n<=15) Subtask1::Main();
if(n<=2000) SubtaskDaoLi::Main();
return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。
不是连续段,连 n^3 都不会了!
不是连续段,连 n^3 都不会了!
不是连续段,连 n^3 都不会了!
猜一个结论:每个划分都最多只有一组元素个数>=2(不考虑相同元素)
有相同元素那就保留在集合里可以拿但是算的时候不算它
那可就会n^2了啊
6
2 4 8 10 5 6
1
11
19
25
31
35
6
2 6 6 3 6 5
1
7
13
19
24
28
居然过大样例了???
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3472kb
input:
7 18 30 10 23 1 3 13
output:
1 31 54 72 85 95 98
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
7 11 12 12 15 30 6 10
output:
1 31 46 58 72 84 96
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
7 14 19 17 12 5 24 3
output:
1 25 44 61 75 87 94
result:
ok 7 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
7 13 15 19 21 27 28 30
output:
1 31 59 86 107 126 153
result:
ok 7 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
7 4 8 12 13 13 13 24
output:
1 25 41 54 67 79 87
result:
ok 7 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
7 21 6 17 20 5 22 27
output:
1 28 50 71 91 108 118
result:
ok 7 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
7 11 17 16 30 24 21 23
output:
1 31 55 78 99 116 142
result:
ok 7 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
7 13 20 16 4 29 26 5
output:
1 30 56 76 92 105 113
result:
ok 7 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
7 25 17 12 16 13 30 30
output:
1 31 61 86 103 119 143
result:
ok 7 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
7 4 8 12 13 13 13 24
output:
1 25 41 54 67 79 87
result:
ok 7 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
7 25 6 29 7 22 14 30
output:
1 31 60 85 107 121 133
result:
ok 7 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
7 21 24 20 30 2 5 21
output:
1 31 55 76 97 117 123
result:
ok 7 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
7 21 19 26 1 28 7 27
output:
1 29 56 82 103 122 129
result:
ok 7 lines
Test #14:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
7 26 11 28 24 30 23 24
output:
1 31 59 85 109 142 166
result:
ok 7 lines
Test #15:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
7 4 8 12 13 13 13 24
output:
1 25 41 54 67 79 87
result:
ok 7 lines
Subtask #2:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #16:
score: 0
Time Limit Exceeded
input:
15 11 28 29 11 13 18 23 1 5 20 24 20 23 3 2
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #31:
score: 0
Runtime Error
input:
100 268 467 21 173 158 287 36 446 36 340 311 283 58 77 464 119 460 198 405 331 214 331 255 157 418 319 354 289 330 64 11 484 186 129 130 368 370 468 292 180 427 76 87 156 13 379 268 170 3 15 263 52 296 242 7 296 376 148 221 270 218 131 326 198 399 132 270 55 299 444 134 222 278 486 409 72 38 193 359...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #51:
score: 0
Runtime Error
input:
1270 1 2 6 7 8 9 10 11 13 14 16 18 19 20 22 23 25 26 28 30 31 32 33 37 38 40 42 43 44 45 46 47 48 49 50 52 53 55 56 57 58 59 62 63 64 67 68 69 70 71 72 74 75 77 78 80 85 86 87 88 89 90 92 96 97 98 99 100 101 103 104 105 107 108 109 113 119 122 124 126 128 132 134 135 137 140 143 144 149 150 151 154 ...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%