QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73775 | #2420. Kitesurfing | WUZRW | WA | 2ms | 3496kb | C++14 | 836b | 2023-01-28 08:45:30 | 2023-01-28 08:45:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
map<ll, ll> f;
ll l[5005], r[5005], s, d, t, n;
ll dfs(ll st) {
if (st >= s) return 0;
ll ans = 1e18;
if (f.count(st)) return f[st];
ll mx = st + d, id = 0;
rep(i, 1, n + 1) {
if (l[i] < mx && mx < r[i]) mx = l[i];
if (l[i] >= st && !id) id = i;
}
ll num = (r[id] - d - st) / d;
if (num > 0) {
f[st] = dfs(st + num * d) + num * min(d, t);
return f[st];
}
rep(i, id, n + 1)
if (l[id] + d >= r[i]) ans = min(ans, min(t, max(0ll, r[i] - d - st)) + t + dfs(r[i]));
else break;
if (id == n + 1) ans = min(ans, s - st);
f[st] = ans;
return ans;
}
signed main() {
cin >> s >> d >> t >> n;
rep(i, 1, n) cin >> l[i] >> r[i];
l[n + 1] = r[n + 1] = s;
cout << dfs(0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3208kb
input:
10 4 5 0
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
10 4 1 0
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
10 4 3 0
output:
8
result:
ok single line: '8'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
4 2 1 1 2 3
output:
2
result:
ok single line: '2'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3304kb
input:
18 10 11 2 3 5 7 14
output:
26
result:
wrong answer 1st lines differ - expected: '23', found: '26'