# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
515542 | 2022-01-19T08:32:32 Z | 79brue | 3단 점프 (JOI19_jumps) | C++14 | 4000 ms | 17680 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, q; int arr[500002]; int DP[5002][5002]; int DPmax[5002][5002]; int sparse[500002][20]; void init(){ for(int i=1; i<=n; i++) sparse[i][0] = arr[i]; for(int d=1; d<20; d++){ for(int i=1; i<=n; i++) sparse[i][d] = max(sparse[i][d-1], (i+(1<<(d-1))) > n ? 0 : sparse[i+(1<<(d-1))][d-1]); } } int query(int l, int r){ int d = 31-__builtin_clz(r-l+1); return max(sparse[l][d], sparse[r-(1<<d)+1][d]); } void solveSmall(){ for(int i=1; i<=n; i++){ DPmax[i][i] = arr[i]; for(int j=i+1; j<=n; j++){ DPmax[i][j] = max(DPmax[i][j-1], arr[j]); } } for(int i=1; i<=n-2; i++) DP[i][i+2] = arr[i] + arr[i+1] + arr[i+2]; for(int d=3; d<n; d++){ for(int i=1; i+d<=n; i++){ int j = i+d; DP[i][j] = max({DP[i][j-1], DP[i+1][j], arr[i] + arr[j] + DPmax[i+1][(i+j)/2]}); } } scanf("%d", &q); while(q--){ int l, r; scanf("%d %d", &l, &r); printf("%d\n", DP[l][r]); } exit(0); } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &arr[i]); // if(n <= 5000) solveSmall(); init(); scanf("%d", &q); while(q--){ int l, r; scanf("%d %d", &l, &r); priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; vector<pair<int, int> > vec; vec.push_back(make_pair(arr[r], r)); vec.push_back(make_pair(arr[r-1], r-1)); for(auto p: vec) pq.push(p); int ans = 0; for(int a=r-2; a>=l; a--){ for(pair<int, int> p: vec){ int b = p.second; if(b-a>1) ans = max(ans, arr[a] + arr[b] + query(a+1, (a+b)/2)); if(b*2<=a+r) ans = max(ans, arr[a] + arr[b] + query(b*2-a, r)); } pq.push(make_pair(arr[a], a)); vec.push_back(make_pair(arr[a], a)); } printf("%d\n", ans); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 292 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 328 KB | Output is correct |
5 | Correct | 2 ms | 300 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 2 ms | 204 KB | Output is correct |
9 | Correct | 2 ms | 296 KB | Output is correct |
10 | Correct | 2 ms | 204 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 292 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 328 KB | Output is correct |
5 | Correct | 2 ms | 300 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 2 ms | 204 KB | Output is correct |
9 | Correct | 2 ms | 296 KB | Output is correct |
10 | Correct | 2 ms | 204 KB | Output is correct |
11 | Execution timed out | 4049 ms | 864 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4066 ms | 17680 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 292 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 328 KB | Output is correct |
5 | Correct | 2 ms | 300 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 2 ms | 204 KB | Output is correct |
9 | Correct | 2 ms | 296 KB | Output is correct |
10 | Correct | 2 ms | 204 KB | Output is correct |
11 | Execution timed out | 4049 ms | 864 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |