Submission #00010

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
#define int long long
int v[3010] = {}, h[3010] = {};
int t[1010] = {}, s[1010] = {};
int dp[1010][3010][2];
int rui1[3010] = {};
int rui2[1010] = {};
signed main(){
int n, m;
cin >> n >> m;
for(int i = 0;i < n;i++) cin >> v[i+1] >> h[i+1];
for(int i = 0;i < m;i++) cin >> t[i+1] >> s[i+1];
dp[0][0][0] = 0;
dp[0][0][1] = LLONG_MIN;
for(int i = 1;i <= n;i++){
dp[0][i][0] = LLONG_MIN;
dp[0][i][1] = LLONG_MIN;
}
for(int i = 0;i < n;i++) rui1[i+1] = rui1[i] + v[i+1];
for(int i = 1;i <= m;i++){
dp[i][0][0] = dp[i-1][0][0] >= s[i-1] ? dp[i-1][0][0] : LLONG_MIN;
dp[i][0][1] = LLONG_MIN;
for(int j = 1; j <= n;j++){
//買わないとき
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]) >= s[i-1] ? max(dp[i-1][j][0], dp[i-1][j][1]) : LLONG_MIN;
//買うとき
if(rui1[j] <= t[i]){
int a1 = dp[i][j-1][0] + h[j];
int a2 = dp[i][j-1][1] + h[j] + abs(h[j]-h[j-1]);
dp[i][j][1] = max(a1, a2);
}else{
dp[i][j][1] = LLONG_MIN;
}
}
}
int ans = -1;
for(int i = n;i >= 0;i--){
if(dp[m][i][0] >= s[m] || dp[m][i][1] >= s[m]){
ans = t[m] - rui1[i];
}
}
cout << ans << endl;
return 0;
}

ステータス

項目 データ
問題 0010 - ゲームの攻略
ユーザー名 ei1719
投稿日時 2019-08-26 00:12:55
言語 C++14
状態 Accepted
得点 20
ソースコード長 1459 Byte
最大実行時間 40 ms
最大メモリ使用量 47892 KB

セット

セット 得点 Cases
1 ALL 20 / 20 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 25 ms 604 KB
1
in02.txt AC 21 ms 408 KB
1
in03.txt AC 26 ms 452 KB
1
in04.txt AC 15 ms 480 KB
1
in05.txt AC 17 ms 504 KB
1
in06.txt AC 14 ms 520 KB
1
in07.txt AC 21 ms 584 KB
1
in08.txt AC 27 ms 540 KB
1
in09.txt AC 22 ms 656 KB
1
in10.txt AC 35 ms 692 KB
1
in11.txt AC 27 ms 2776 KB
1
in12.txt AC 22 ms 2900 KB
1
in13.txt AC 19 ms 6868 KB
1
in14.txt AC 23 ms 23504 KB
1
in15.txt AC 32 ms 47628 KB
1
in16.txt AC 32 ms 47656 KB
1
in17.txt AC 17 ms 580 KB
1
in18.txt AC 17 ms 520 KB
1
in19.txt AC 25 ms 584 KB
1
in20.txt AC 21 ms 644 KB
1
in21.txt AC 17 ms 576 KB
1
in22.txt AC 18 ms 6904 KB
1
in23.txt AC 29 ms 38132 KB
1
in24.txt AC 31 ms 47708 KB
1
in25.txt AC 28 ms 47740 KB
1
in26.txt AC 30 ms 47772 KB
1
in27.txt AC 40 ms 47808 KB
1
in28.txt AC 30 ms 47840 KB
1
in29.txt AC 33 ms 47740 KB
1
in30.txt AC 30 ms 47892 KB
1