QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#866093#7304. Coins 2SFlyerAC ✓311ms88192kbC++141.2kb2025-01-22 11:51:322025-01-22 11:51:38

Judging History

你现在查看的是最新测评结果

  • [2025-01-22 11:51:38]
  • 评测
  • 测评结果:AC
  • 用时:311ms
  • 内存:88192kb
  • [2025-01-22 11:51:32]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int L = 360360;

ll n,m,a[20],s;

ll lcm(ll x,ll y){
	return x/__gcd(x,y)*y;
}

ll f[15*L*2+5];

void solve(){
	s=0,m=1;
	for (int i=1; i<=n; i++){
		m=lcm(m,i);
		cin>>a[i];
		s+=a[i]*i;
	}
	for (int i=0; i<2*n*m; i++) f[i]=1e9;
	f[0]=0;
	for (int i=1; i<=n; i++){
		for (int j=0; j<2*n*m; j++) if (j>=i && f[j-i]<a[i]) f[j]=min(f[j],f[j-i]+1);
		for (int j=0; j<2*n*m; j++) f[j]=f[j]<=a[i]?0:1e9;
	}
	ll ans=0;
	if (s<2*n*m){
		for (int i=0; i<=s; i++) ans+=!f[i];
	}
	else{
		for (int i=0; i<n*m; i++) ans+=!f[i];
		ans*=2;
		for (int i=0; i<m; i++) ans+=(!f[(n-1)*m+i])*(s-n*m-(n-1)*m-i)/m;
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	while (cin>>n){
		solve();
	}
	return 0;
}

// TRY! TRY! TRY!

/*
Think twice before coding. Have you overkilled?
Think twice before submitting.
Check on the samples and constraints carefully.
*/

/*
Be brave to guess.
Is your former/first approach correct?
Follow your intuition.
Use a notebook to note down your ideas and check whether they are correct.
*/

/*
A simple brute force may work? There is some limit on the answer?
Try to find patterns.
*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

3
0 1 2
3
0 2 3

output:

6
12

result:

ok 2 number(s): "6 12"

Test #2:

score: 0
Accepted
time: 311ms
memory: 88020kb

input:

1
0
15
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

1
120000000001

result:

ok 2 number(s): "1 120000000001"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

5
0 2 1 0 0
5
0 0 0 0 53
5
0 6 3 0 0
5
1 0 0 0 1
5
1 0 0 0 0
5
2 0 0 0 116
5
2 0 0 0 0
5
1 0 1 106 1356
5
0 2 0 0 7926
5
0 0 2 1 2004
5
1 0 0 0 1
5
0 0 0 1 5
5
0 0 0 0 0
5
0 1 32840 0 1
5
2 0 0 0 12
5
2 0 0 1 1
5
0 1 79 56770 10
5
1 0 0 1 0
5
0 1 1 2 52165
5
0 0 0 0 1
5
0 0 1 13 0
5
0 0 0 1 10
5
0 0...

output:

6
54
20
4
2
351
3
7207
23781
10027
4
12
1
98524
39
10
227368
4
260837
2
28
22
114
78
76
4
280
233
8
1
12
214572
10
2
1
1
2
108
17760
15926
250077
55576
4
104
282
45419
1687
2973
8
28482
6
4
2988
8
10
102
4
793
69
2
7624
4
181850
84
36589
3
2832
11
25
2
32457
127
33099
2
3
8
116
4
6
260
4
6
29027
4
2...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

5
0 0 0 0 7282
5
1 0 1 1 1
5
0 100 1 6466 131627995
5
2 0 0 0 1
5
2 0 0 0 0
5
0 0 0 0 2
5
3 0 0 0 24
5
1 0 0 0 0
5
2 0 0 1033661 1
5
2 0 0 0 1
5
1 0 2 1 0
5
1 0 0 74999942 1
5
0 0 16 5 1
5
0 0 14 1 1
5
0 0 0 94148 2
5
1 0 0 0 0
5
0 4 66108 1 1
5
0 0 0 1 0
5
0 2 0 0 0
5
0 0 26609277 2057266 32110772
...

output:

7283
12
658166041
6
3
3
100
2
4134650
6
10
224999830
70
48
282447
2
198340
2
3
248610752
3064
6608762
27104217
88460
1225544
2128
206314
4247620
4756202
2
43189704
4
23417
1151
10
174058
1073133147
4852
2
2
10
77870412
6
13616297
6040750
624815262
1854
300636553
1
4
6
31145401
935098
6
82785138
132
...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 56ms
memory: 5920kb

input:

10
0 0 0 133395012 1 64 1 1 1 29
10
1 0 0 2871 869717 68 15569 112946 431 0
10
2 0 0 0 0 0 0 0 1 1
10
1 0 0 0 0 0 1 1 1 1
10
0 0 0 0 0 0 0 0 0 1
10
0 208 3 0 60131558 184254 1 909 166293 1
10
1 0 0 0 0 0 0 0 0 24784
10
1 0 0 0 1 1 1 26206816 1 0
10
4 0 0 0 0 62468533 1052 0 0 27715813
10
0 0 0 0 0 0...

output:

533580746
5376905
10
20
2
303267664
49570
209654551
651976695
111
9859639
4237557
3045713
509037116
305067
6
25
1852794
2398551872
1651057262
22708645
245970222
110782837
385654273
724791161
56
4
666
100200177
44102430
1298591
9
110583641
7717333
20
612738350
455682
2857417747
135486
4
1103222425
35...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 260ms
memory: 88116kb

input:

15
6 0 0 0 0 0 0 0 0 0 0 0 51010 0 1

output:

459104

result:

ok 1 number(s): "459104"

Test #7:

score: 0
Accepted
time: 265ms
memory: 88192kb

input:

15
6 0 0 0 0 0 0 0 0 15052 1 0 6920899 1 639

output:

90131818

result:

ok 1 number(s): "90131818"

Test #8:

score: 0
Accepted
time: 280ms
memory: 88056kb

input:

15
3 0 0 0 3 43 2 0 6 3916571 0 4106 25560554 1 44

output:

371503201

result:

ok 1 number(s): "371503201"

Test #9:

score: 0
Accepted
time: 267ms
memory: 88184kb

input:

15
9 0 0 0 0 0 0 0 0 0 1 1 352 51 0

output:

5321

result:

ok 1 number(s): "5321"

Test #10:

score: 0
Accepted
time: 289ms
memory: 88080kb

input:

15
1 0 0 0 0 0 7 2050510 0 1 6571321 2097618 1349 893 1

output:

113890132

result:

ok 1 number(s): "113890132"

Test #11:

score: 0
Accepted
time: 306ms
memory: 88048kb

input:

15
0 0 90610226 2 1 9005 0 1 9 1 44 19 1 966676 1

output:

285419021

result:

ok 1 number(s): "285419021"

Test #12:

score: 0
Accepted
time: 300ms
memory: 88092kb

input:

15
4 0 0 0 0 0 0 0 0 0 0 0 230110792 158832450 4087

output:

5215155866

result:

ok 1 number(s): "5215155866"

Test #13:

score: 0
Accepted
time: 285ms
memory: 88060kb

input:

15
1 0 0 0 3 0 0 350364383 4859 3618 356965 5942367 175260 1 0

output:

2880508397

result:

ok 1 number(s): "2880508397"

Test #14:

score: 0
Accepted
time: 279ms
memory: 88036kb

input:

15
1 0 0 0 1 0 1 0 53297877 0 1 25736 0 1 54519258

output:

1297778628

result:

ok 1 number(s): "1297778628"

Test #15:

score: 0
Accepted
time: 288ms
memory: 88136kb

input:

15
3 0 0 0 2 2656013 0 0 42 3 33 1 86626609 0 1

output:

1142082805

result:

ok 1 number(s): "1142082805"

Test #16:

score: 0
Accepted
time: 55ms
memory: 3968kb

input:

10
24 0 0 0 0 0 43 41 39 0
10
0 2 16 0 2 0 0 0 0 0
10
8 0 0 0 0 0 6 0 8 0
10
49 0 0 0 0 0 225 117 134 127
10
5 0 0 0 0 0 7 8 0 0
10
4 0 0 0 0 0 9 7 0 0
10
5 0 0 0 0 0 0 0 11 9
10
25 0 0 47 60 64 345 46 102 44
10
13 0 0 0 0 0 0 21 27 29
10
0 0 0 25 17 0 0 0 9 10
10
12 0 0 0 0 0 0 0 8 9
10
4 0 0 0 0 5...

output:

1005
61
123
5037
117
118
183
5039
715
355
175
185
93
353
279
720
87
194
173
1259
145
555
5038
171
182
151
137
710
1007
189
713
187
5035
137
145
118
173
147
177
171
1001
713
163
708
175
341
190
119
719
57
143
73
694
2519
715
90
5039
137
111
140
1677
5035
177
5041
171
70
161
1005
179
5035
175
171
109
...

result:

ok 100 numbers

Extra Test:

score: 0
Extra Test Passed