QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474578 | #366. Long Distance Coach | ltunjic | 0 | 0ms | 1660kb | C++20 | 1.1kb | 2024-07-12 20:28:17 | 2024-07-12 20:28:17 |
answer
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 2010;
int n, m;
ll s[N], d[N], c[N], t, w;
int fst[N], ind[N]; // -1
ll dp[N];
int main() {
ll X;
scanf("%lld%d%d%lld%lld", &X, &n, &m, &w, &t);
s[n + 1] = X;
for(int i = 1; i <= n; ++i) { scanf("%lld", s + i); }
ll sum = (X / t + 1LL) * w;
for(int i = 0; i < m; ++i) {
scanf("%lld%lld", d + i, c + i);
sum += c[i];
ind[i] = i;
}
sort(ind, ind + m, [](ll a, ll b) {
return d[a] < d[b];
});
sort(s, s + n + 2, [](ll a, ll b) {
return a < b;
});
memset(fst, -1, sizeof(fst));
for(int j = m - 1; j >= 0; --j) {
int x = ind[j];
dp[j] = dp[j + 1] - c[x] + ((X - d[x]) / t + 1LL) * w;
for(int i = 1; i <= n + 1; ++i) {
ll k = (s[i] - d[x]) / t;
if(d[x] + k * t > s[i - 1] && (k + 1LL) * t > s[i]) {
if(fst[i] == -1) { fst[i] = j; }
dp[j] = min(dp[j], dp[fst[i] + 1] + (ll) k * w * (ll) (fst[i] - j + 1));
}
}
}
printf("%lld\n", sum + dp[0]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1660kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
250000000000000003
result:
wrong answer 1st lines differ - expected: '499999999999000003', found: '250000000000000003'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%