Submission #00148

ソースコード

?
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x), end(x)
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int_fast64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
template <class Func>
class FixPoint : Func {
public:
explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
template <class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
return FixPoint<Func>{forward<Func>(f)};
}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> inline void bye(T x) { cout << x << '\n'; exit(0); }
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> v(n + 1), h(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> v[i] >> h[i];
}
vector<int> t(m + 2), s(m + 2);
for (int i = 1; i <= m; ++i) {
cin >> t[i] >> s[i];
}
t.push_back(INF);
// dp[i][j]: i番目まで攻略して、j番目までアイテムを購入した時の強さの最大
vector dp(m + 1, vector(n + 1, -1LL));
dp[0].assign(n + 1, 0LL);
for (int i = 1; i <= m; ++i) {
int r = 0, vsum = 0;
for (int j = 0; j <= n; ++j) {
vsum += v[j];
if (vsum > t[i]) break;
r = j;
}
int p, hsum, st;
for (int j = 0; j <= n; ++j) {
if (dp[i - 1][j] != -1) {
hsum = dp[i - 1][j];
dp[i][j] = hsum;
p = j + 1;
st = j;
break;
}
}
h.push_back(h.back());
if (dp[i][st] < s[i]) dp[i][st] = -1;
for (int j = st + 1; j <= r; ++j) {
if (j == p) {
hsum += h[j];
} else if (p < j) {
hsum += h[j] + abs(h[j - 1] - h[j]);
}
if (dp[i - 1][j] <= hsum) {
dp[i][j] = hsum;
} else {
dp[i][j] = dp[i - 1][j];
if (dp[i - 1][j] + h[j + 1] > hsum + abs(h[j] - h[j + 1]) + h[j + 1]){
hsum = dp[i - 1][j];
p = j + 1;
}
}
if (dp[i][j] < s[i]) dp[i][j] = -1;
}
}
// for (int i = 0; i <= m; ++i) {
// for (int j = 0; j <= n; ++j) {
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
int res = -INF, vsum = 0;
for (int i = 1; i <= n; ++i) {
vsum += v[i];
if (dp.back()[i] == -1) continue;
chmax(res, t[m] - vsum);
}
if (res == -INF) {
cout << -1 << '\n';
} else {
cout << res << '\n';
}
return 0;
}

ステータス

項目 データ
問題 0010 - ゲームの攻略
ユーザー名 有象無象
投稿日時 2021-07-28 11:33:50
言語 C++17
状態 Accepted
得点 20
ソースコード長 3780 Byte
最大実行時間 40 ms
最大メモリ使用量 24460 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 22 ms 476 KB
1
in02.txt AC 20 ms 556 KB
1
in03.txt AC 22 ms 636 KB
1
in04.txt AC 21 ms 584 KB
1
in05.txt AC 19 ms 536 KB
1
in06.txt AC 26 ms 612 KB
1
in07.txt AC 14 ms 568 KB
1
in08.txt AC 27 ms 640 KB
1
in09.txt AC 24 ms 592 KB
1
in10.txt AC 20 ms 656 KB
1
in11.txt AC 16 ms 592 KB
1
in12.txt AC 28 ms 524 KB
1
in13.txt AC 24 ms 560 KB
1
in14.txt AC 26 ms 2604 KB
1
in15.txt AC 34 ms 24224 KB
1
in16.txt AC 38 ms 24216 KB
1
in17.txt AC 18 ms 532 KB
1
in18.txt AC 23 ms 484 KB
1
in19.txt AC 19 ms 560 KB
1
in20.txt AC 17 ms 516 KB
1
in21.txt AC 26 ms 592 KB
1
in22.txt AC 23 ms 552 KB
1
in23.txt AC 25 ms 5548 KB
1
in24.txt AC 40 ms 24224 KB
1
in25.txt AC 31 ms 24344 KB
1
in26.txt AC 38 ms 24336 KB
1
in27.txt AC 39 ms 24336 KB
1
in28.txt AC 40 ms 24460 KB
1
in29.txt AC 36 ms 24324 KB
1
in30.txt AC 37 ms 24320 KB
1