| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038858 |
2024-07-30T08:24:19 Z |
김은성(#10985) |
Tower (JOI24_tower) |
C++17 |
|
2000 ms |
91984 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3ffffffffffffff;
ll dp[6009][2009], l[200009], r[200009], basic[200009];
deque<int> q;
int main(){
int n, t, i, j=0, k;
ll d, a, b;
scanf("%d %d", &n, &t);
scanf("%lld %lld %lld", &d, &a, &b);
for(i=1; i<=n; i++){
scanf("%lld %lld", &l[i], &r[i]);
l[i]--;
r[i]++;
}
l[n+1] = (ll)1e16;
if(b > a*d){
dp[0][0] = 0;
for(i=1; i<=n; i++)
dp[0][i] = -1;
for(k=1; k<=n; k++){
j = 0;
deque<int> q;
dp[k][0] = -1;
for(i=1; i<=n; i++){
if(dp[k-1][i-1] != -1)
q.push_back(i-1);
if(r[i] - l[i] > d)
continue;
while(l[j+1] < r[i] - d){
if(q.front() == j)
q.pop_front();
j++;
}
if(q.empty())
dp[k][i] = -1;
else{
dp[k][i] = max(dp[k-1][q.front()] + d, r[i]);
if(dp[k][i] > l[i+1])
dp[k][i] = -1;
}
}
}
for(i=1; i<=t; i++){
ll x;
scanf("%lld", &x);
int idx = lower_bound(l+1, l+n+1, x) - l;
idx--;
for(j=0; j<=n; j++){
if(dp[j][idx] == -1 || dp[j][idx] > x)
continue;
printf("%lld\n", x + j * (b-a*d));
break;
}
if(j==n+1)
printf("-1\n");
}
}
else{
dp[0][0] = 0;
for(i=1; i<=n; i++)
dp[0][i] = -1;
for(k=1; k<=3*n+4; k++){
j = 0;
dp[k][0] = (l[1] >= d*k ? (d*k) : -1);
q.clear();
for(i=1; i<=n; i++){
if(dp[k-1][i-1] != -1)
q.push_back(i-1);
while(l[j+1] < r[i] - d){
if(q.front() == j)
q.pop_front();
j++;
}
//if(k >= 2000)
//printf("q.sz=%d\n", q.size());
if(q.empty())
dp[k][i] = -1;
else{
dp[k][i] = max(dp[k-1][q.front()] + d, r[i]);
if(dp[k][i] > l[i+1])
dp[k][i] = -1;
}
if(k >= 2){
if(dp[k-2][i-1] == -1 || l[i]-r[i-1] < d)
continue;
ll delta = (l[i] - r[i-1]) % d + ((l[i]-r[i-1] >= 2*d) ? d : 0);
if(dp[k-2][i-1] - r[i-1] <= delta){
ll temp = max(l[i] - (delta - (dp[k-2][i-1] - r[i-1])) + d, r[i]);
//printf("temp=%lld delta=%lld\n", temp, delta);
if(temp >= r[i] && temp <= l[i+1] && r[i]-l[i] <= d){
if(dp[k][i] == -1 || dp[k][i] > temp)
dp[k][i] = temp;
}
}
}
if(k >= 3){
if(dp[k-3][i-1] == -1 || l[i]-r[i-1] < 2*d)
continue;
ll delta = (l[i] - r[i-1]) % d;
if(dp[k-3][i-1] - r[i-1] <= delta){
ll temp = max(l[i] - (delta - (dp[k-3][i-1] - r[i-1])) + d, r[i]);
//printf("temp=%lld delta=%lld\n", temp, delta);
if(temp >= r[i] && temp <= l[i+1] && r[i]-l[i] <= d){
if(dp[k][i] == -1 || dp[k][i] > temp)
dp[k][i] = temp;
}
}
}
}
//if(k >=2000){
// for(i=0; i<=n; i++){
// printf("dp[%d][%d]=%lld\n", k, i, dp[k][i]);
// }
//}
}
basic[0] = 0;
for(i=2; i<=n; i++)
basic[i] = basic[i-1] + max((l[i]-r[i-1])/d - 2, 0ll);
for(i=1; i<=t; i++){
ll x;
scanf("%lld", &x);
int idx = lower_bound(l+1, l+n+1, x) - l;
idx--;
ll ans = INF;
for(j=3*n+4; j>=0; j--){
if(dp[j][idx] == -1 || dp[j][idx] > x)
continue;
ans = min(ans, x*a + (j+basic[idx] + (x-dp[j][idx])/d) * (b-a*d));
}
if(ans==INF)
ans=-1;
printf("%lld\n", ans);
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | scanf("%d %d", &n, &t);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | scanf("%lld %lld %lld", &d, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%lld %lld", &l[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
8788 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4584 KB |
Output is correct |
| 3 |
Correct |
186 ms |
91984 KB |
Output is correct |
| 4 |
Execution timed out |
2084 ms |
26472 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
