QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#462989#7646. 优惠购物bribritt0 1ms3748kbC++17618b2024-07-04 10:54:262024-07-04 10:54:27

Judging History

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

  • [2024-07-04 10:54:27]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3748kb
  • [2024-07-04 10:54:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
  int n, m, c; cin >> n >> m >> c;
  int a[n], b[n];
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  int dp[n+1][755];
  for(int i=0;i<=n;i++) for(int j=0;j<755;j++) dp[i][j]=2e15;
  dp[0][m]=0;
  for(int i=1;i<=n;i++) for(int j=0;j<=b[i-1];j++) {
    int delt = j - (a[i-1]-j)/c;
    for(int k=max(0LL,-delt);k<755+min(0LL,-delt);k++) dp[i][k]=min(dp[i][k],dp[i-1][k+delt]+(a[i-1]-j));
  }
  cout << *min_element(dp[n],dp[n]+755)<<"\n";
}
main() {
  int t; cin >> t;
  while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 1ms
memory: 3664kb

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: 0ms
memory: 3748kb

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: -5
Wrong Answer
time: 1ms
memory: 3692kb

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
63
51

result:

wrong answer 4th lines differ - expected: '64', found: '63'

Subtask #2:

score: 0
Runtime Error

Test #4:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Time Limit Exceeded

Test #24:

score: 0
Time Limit Exceeded

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:

2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000
2000000000000000

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%