# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1038728 | 2024-07-30T06:59:53 Z | 김은성(#10985) | Tower (JOI24_tower) | C++17 | 4 ms | 8796 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[4009][2009], l[200009], r[200009], basic[200009]; 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; assert(b < a*d); 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); 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<=2*n+4; 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); 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; } 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; if(dp[k-2][i-1] - r[i-1] <= delta){ ll temp = l[i] - (delta - (dp[k-2][i-1] - r[i-1])) + d; if(temp >= r[i]){ if(dp[k][i] == -1 || dp[k][i] > temp) dp[k][i] = temp; } } } } } basic[0] = 0; for(i=1; i<=n; i++) basic[i] = basic[i-1] + max((r[i]-l[i-1])/d - 1, 0ll); for(i=1; i<=t; i++){ ll x; scanf("%lld", &x); //printf("i=%d t=%d x=%lld\n", i,t, x); int idx = lower_bound(l+1, l+n+1, x) - l; idx--; for(j=2*n+4; j>=0; j--){ if(dp[j][idx] == -1 || dp[j][idx] > x) continue; printf("%lld\n", x + (j+basic[idx] + (x-dp[j][idx])/d) * (b-a*d)); break; } if(j==-1) printf("-1\n"); } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 8796 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |