QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463089#7646. 优惠购物TheRaptor15 238ms982156kbC++141.3kb2024-07-04 13:38:242024-07-04 13:38:25

Judging History

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

  • [2024-07-04 13:38:25]
  • 评测
  • 测评结果:15
  • 用时:238ms
  • 内存:982156kb
  • [2024-07-04 13:38:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		long long m,c;
		cin >> n >> m >> c;
		pair<long long,long long> arr[n];
		for(int i=0; i<n; i++) cin >> arr[i].first;
		for(int i=0; i<n; i++) cin >> arr[i].second;
		if(n<=500){
			long long dp[n+1][250005];
			memset(dp,-1,sizeof(dp));
			dp[0][m]=0;
			for(int i=0; i<n; i++){
				for(int j=0; j<=250000; j++){
					if(dp[i][j]==-1) continue;
					for(int k=0; k<=min(arr[i].second,(long long)j); k++){
						int nc=j-k+(arr[i].first-k)/c;
						if(dp[i+1][nc]==-1) dp[i+1][nc]=dp[i][j]+arr[i].first-k;
						else dp[i+1][nc]=min(dp[i+1][nc],dp[i][j]+arr[i].first-k);
					}
				}
			}
			long long ans=1e16;
			for(int i=0; i<=250000; i++){
				if(dp[n][i]!=-1) ans=min(ans,dp[n][i]);
			}
			cout << ans << '\n';
		}
		else{
			long long ans=0;
			for(int i=0; i<n; i++){
				long long can=min({arr[i].second,arr[i].first%c,m});
				m-=can;
				ans+=arr[i].first-can;
				arr[i].first-=can;
				arr[i].second-=can;
				m+=arr[i].first/c;
			}
			for(int i=n-1; i>=0; i--){
				m-=arr[i].first/c;
				long long can=min({arr[i].first,m,arr[i].second});
				ans-=can;
				m-=can;
			}
			cout << ans << '\n';
		}
	}
}


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 17ms
memory: 25040kb

input:

5
10 9 8
10 5 1 2 10 9 2 9 8 8
5 3 1 1 7 2 2 1 3 0
10 1 5
3 2 6 10 5 10 1 4 8 1
1 2 5 6 2 3 1 3 6 1
10 6 10
5 4 9 5 4 10 8 5 2 4
2 4 2 5 1 1 7 5 0 0
10 5 10
6 2 7 4 3 8 10 5 5 4
1 0 6 3 3 5 4 5 0 0
10 6 12
6 8 7 3 1 4 10 2 9 10
0 3 1 3 1 3 1 0 4 7

output:

51
42
49
48
54

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 19ms
memory: 25120kb

input:

5
10 8 16
2 4 3 3 10 1 8 7 1 10
2 1 1 2 9 0 2 2 1 0
10 6 5
1 8 7 1 5 1 2 5 5 2
1 6 0 0 4 1 0 0 0 0
10 9 9
10 5 3 1 2 1 9 3 1 10
3 0 2 0 2 1 8 2 1 9
10 4 8
1 4 7 9 2 4 7 9 4 6
1 3 2 4 1 0 4 0 4 2
10 10 7
5 1 6 4 7 5 10 6 2 7
2 0 3 4 5 4 7 4 2 1

output:

41
29
34
47
41

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 15ms
memory: 25060kb

input:

5
10 2 18
2 7 3 1 2 2 10 3 10 9
1 7 2 0 1 1 8 2 8 8
10 6 17
10 7 9 6 8 2 9 5 5 4
10 1 5 5 3 0 4 1 2 2
10 5 10
1 6 3 8 7 7 7 9 7 4
0 3 2 4 1 0 5 5 4 2
10 2 7
6 2 9 9 3 8 7 8 10 10
1 0 8 3 2 2 0 2 1 2
10 6 12
7 10 8 1 2 4 7 8 3 7
6 10 1 0 0 4 0 8 1 0

output:

47
59
54
64
51

result:

ok 5 lines

Subtask #2:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 128ms
memory: 19204kb

input:

1
1000000 75424149 4
15519624 393474467 66570532 20552964 884794646 633920424 885627436 891022137 207531470 263467015 853563838 909020263 225156643 843397191 555130236 28501962 70380880 400094075 351542363 118716292 772000502 495729611 777038576 845271464 346378405 179347308 90713310 683636539 92786...

output:

500014428858584

result:

wrong answer 1st lines differ - expected: '400011543086868', found: '500014428858584'

Subtask #3:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 10
Accepted
time: 235ms
memory: 982116kb

input:

1
500 225 2
0 0 2 1 2 1 4 0 0 0 0 0 2 1 2 0 0 1 0 0 1 1 2 0 2 2 3 1 0 0 2 2 0 1 1 2 1 3 1 3 2 0 0 1 2 0 2 0 0 1 1 0 1 1 1 0 1 0 2 3 0 0 1 3 1 0 2 2 1 1 4 1 1 2 1 1 0 3 2 0 0 0 1 3 0 1 0 1 2 1 0 0 2 1 1 1 2 3 2 2 2 1 1 2 2 0 0 1 1 0 0 1 0 1 1 0 1 3 1 2 0 2 2 1 1 2 0 1 0 4 2 0 0 0 0 1 4 1 0 1 0 1 0 0 ...

output:

231

result:

ok single line: '231'

Test #8:

score: 0
Accepted
time: 238ms
memory: 982156kb

input:

1
500 253 10
1 2 1 1 0 0 1 3 3 1 0 0 0 0 0 0 0 2 1 0 0 2 1 0 0 0 2 0 0 1 2 1 0 2 2 1 1 2 1 0 2 1 0 0 0 1 0 2 2 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 2 0 1 0 0 1 1 1 0 0 0 1 2 2 1 1 1 0 3 1 0 0 0 1 0 1 1 4 3 1 0 0 0 1 0 1 3 1 1 1 1 4 1 0 0 0 1 1 1 2 2 0 0 3 0 0 1 0 2 2 1 0 2 0 1 0 2 0 0 1 1 0 2 1 0 1 1 1 0 0...

output:

278

result:

ok single line: '278'

Test #9:

score: 0
Accepted
time: 173ms
memory: 15272kb

input:

100
5 3 11
0 1 3 0 1
0 0 0 0 0
5 3 11
0 0 2 2 1
0 0 0 1 1
5 3 10
2 1 0 1 1
2 1 0 0 1
5 3 11
2 2 0 0 1
0 0 0 0 1
5 2 11
0 0 4 0 1
0 0 3 0 1
5 5 10
2 0 0 0 3
1 0 0 0 1
5 5 11
3 1 1 0 0
3 0 1 0 0
5 2 11
0 1 2 0 2
0 1 2 0 0
5 4 10
2 1 1 1 0
0 1 0 1 0
5 4 10
1 1 1 2 0
1 0 1 2 0
5 2 11
2 0 3 0 0
1 0 3 0 0...

output:

5
3
2
4
3
3
1
3
3
1
3
3
4
1
3
3
1
4
3
4
2
5
3
4
4
2
4
2
2
3
4
4
3
3
2
3
0
2
3
4
4
3
3
2
2
4
5
2
4
4
3
3
4
3
4
2
3
3
3
2
4
4
5
2
4
2
4
2
3
4
4
4
4
2
2
1
2
4
1
3
4
3
3
0
3
5
5
2
4
3
2
3
4
3
3
4
2
3
5
3

result:

ok 100 lines

Test #10:

score: 0
Accepted
time: 158ms
memory: 25108kb

input:

50
10 4 11
2 0 0 2 0 0 1 1 4 0
2 0 0 1 0 0 1 1 2 0
10 9 11
0 1 2 0 1 1 1 2 2 0
0 0 2 0 1 0 1 1 2 0
10 4 11
1 2 1 3 0 0 2 0 1 0
1 0 1 3 0 0 0 0 0 0
10 9 10
1 0 1 1 2 1 0 1 2 1
1 0 0 0 2 0 0 1 0 0
10 7 11
0 3 0 2 3 0 0 2 0 0
0 3 0 0 3 0 0 2 0 0
10 9 10
0 1 0 1 1 1 1 2 1 2
0 0 0 0 1 1 1 0 0 0
10 6 11
0...

output:

6
3
6
6
3
7
7
6
2
7
3
6
8
4
6
5
3
5
8
8
6
5
7
8
8
8
4
8
5
4
3
5
7
5
4
8
5
5
7
6
7
6
7
8
8
4
2
4
7
6

result:

ok 50 lines

Subtask #4:

score: 0
Wrong Answer

Dependency #3:

100%
Accepted

Test #11:

score: 10
Accepted
time: 200ms
memory: 25096kb

input:

60
10 17 2
14 8 11 5 9 14 9 9 8 13
12 3 8 5 9 1 0 4 2 10
10 13 2
11 11 10 15 8 12 7 8 8 10
11 6 3 8 2 4 7 8 1 4
10 7 2
18 6 15 6 11 6 12 8 9 9
15 0 9 0 5 6 0 6 4 3
10 4 3
12 8 16 11 9 5 6 9 10 14
0 0 5 7 8 1 6 2 1 5
10 23 3
10 14 11 7 9 7 7 12 17 6
5 8 1 5 5 7 7 1 4 3
10 27 3
13 7 11 12 11 12 10 9 9...

output:

57
60
64
75
60
55
68
67
62
76
76
69
71
61
73
60
54
62
62
67
61
71
75
64
63
73
73
56
65
67
63
40
40
46
57
58
53
64
64
46
42
30
39
46
61
54
55
48
64
51
55
57
57
73
40
63
56
70
55
38

result:

ok 60 lines

Test #12:

score: 0
Accepted
time: 194ms
memory: 25092kb

input:

60
10 4 2
6 14 13 9 5 12 14 12 8 7
2 11 3 3 5 2 11 1 3 2
10 14 3
12 11 5 11 13 12 14 5 9 8
12 9 4 11 2 7 4 4 1 3
10 39 3
8 11 9 17 4 16 7 6 15 7
8 2 9 8 3 12 7 1 2 2
10 4 2
9 15 12 11 10 8 6 7 10 12
9 2 6 3 8 1 3 3 4 0
10 4 2
13 10 9 8 7 6 15 11 15 6
8 3 7 2 2 5 0 0 7 2
10 18 3
12 9 8 8 9 9 11 12 9 ...

output:

68
66
49
70
71
64
71
67
73
69
66
65
66
69
60
66
76
64
68
69
68
67
77
67
60
71
76
67
62
65
52
67
48
73
61
51
48
71
40
60
50
49
60
49
66
52
35
68
52
45
32
69
64
56
48
66
58
67
57
50

result:

ok 60 lines

Test #13:

score: -10
Wrong Answer
time: 1ms
memory: 3724kb

input:

6
1000 129 2
0 1 1 0 3 2 0 0 3 0 0 1 0 1 1 0 0 0 0 3 0 1 2 1 3 1 2 2 1 1 1 0 1 1 0 0 1 1 2 1 2 0 1 0 0 1 1 2 1 1 0 0 1 0 1 0 1 0 0 1 2 1 2 2 0 0 0 0 1 1 1 1 0 0 1 0 3 1 0 1 1 2 2 1 0 1 1 3 0 1 1 2 0 0 1 1 0 1 1 2 2 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 2 1 1 2 2 1 0 1 1 0 2 1 0 0 2 0 0 4 1 1...

output:

871
636
979
618
695
515

result:

wrong answer 1st lines differ - expected: '648', found: '871'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Runtime Error

Test #24:

score: 0
Runtime Error

input:

600
10 21 2
1434256 1792820 8964100 10756920 6454152 717128 9681228 7529844 7171280 10398356
1075692 1075692 1434256 10039792 358564 717128 717128 5737024 3227076 1792820
10 5 4
5500368 6875460 4125274 687544 5500368 4469049 4125276 2750183 9969416 5156593
4469049 3781503 687546 0 1718865 343773 0 2...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #6:

0%

Subtask #9:

score: 0
Skipped

Dependency #2:

0%