QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#761504 | #6606. The Boomsday Project | fosov | ML | 2ms | 14060kb | C++14 | 1.4kb | 2024-11-18 23:47:00 | 2024-11-18 23:47:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>
#define pdd pair<double, double>
#define N 400010
#define K 550
int n, m, r;
ll d[N], k[N], c[N], cp[K][N];
ll dp[N];
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> r;
for (int i = 0; i < n; ++ i) cin >> d[i] >> k[i] >> c[i];
vector<int> rc;
for (int i = 0; i < m; ++ i) {
int p, q; cin >> p >> q;
for (int j = 0; j < q; ++ j) {
rc.emplace_back(p);
}
}
sort(rc.begin(), rc.end());
int sz = rc.size();
for (int i = 0; i < sz; ++ i) dp[i] = LNF;
for (int i = 0; i < n; ++ i) {
int nxt = 0;
for (int j = 0; j < sz; ++ j) {
nxt = max(nxt, j);
while (nxt < sz && rc[nxt] <= rc[j] + d[i] - 1 && nxt - j < k[i]) ++ nxt;
cp[i][j] = nxt;
}
}
for (int i = sz-1; i >= 0; -- i) {
dp[i] = min(dp[i], dp[i+1] + r);
for (int j = 0; j < n; ++ j) {
assert(cp[j][i] > i);
dp[i] = min(dp[i], dp[cp[j][i]] + c[j]);
}
}
cout << dp[0] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13748kb
input:
2 1 10 1 3 12 1 2 9 1 10
output:
42
result:
ok 1 number(s): "42"
Test #2:
score: 0
Accepted
time: 0ms
memory: 14060kb
input:
2 4 10 1 3 12 1 2 9 1 3 2 3 3 3 4 1
output:
45
result:
ok 1 number(s): "45"
Test #3:
score: -100
Memory Limit Exceeded
input:
500 100 1000 95 20 20892 73 627 55354 52 747 1404314 19 676 597007 65 814 1569851 91 397 691575 81 4 4575 97 382 624404 21 197 201850 67 799 643576 27 895 1510533 3 800 552439 49 954 1149851 70 892 676406 82 882 1348956 1 318 324094 43 238 439111 94 397 471003 16 119 130686 1 637 77731 79 292 35234 ...
output:
450790