# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
515525 | 2022-01-19T08:24:05 Z | 79brue | 3단 점프 (JOI19_jumps) | C++14 | 4000 ms | 4712 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]; 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(); scanf("%d", &q); while(q--){ int l, r; scanf("%d %d", &l, &r); int ans = 0; for(int a=l; a<=r-2; a++){ vector<pair<int, int> > vec; for(int j=a+1; j<=r; j++) vec.push_back(make_pair(arr[j], j)); sort(vec.rbegin(), vec.rend()); for(int j=0; j<(int)vec.size() && j<2; j++){ for(int k=a+1; k<=r; k++){ if(vec[j].second == k) continue; int b = min(vec[j].second, k); int c = max(vec[j].second, k); if(b-a <= c-b) ans = max(ans, arr[a]+arr[b]+arr[c]); } } } printf("%d\n", ans); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 4 ms | 304 KB | Output is correct |
3 | Correct | 2 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 204 KB | Output is correct |
5 | Correct | 3 ms | 204 KB | Output is correct |
6 | Correct | 4 ms | 204 KB | Output is correct |
7 | Correct | 4 ms | 320 KB | Output is correct |
8 | Correct | 4 ms | 204 KB | Output is correct |
9 | Incorrect | 6 ms | 204 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 4 ms | 304 KB | Output is correct |
3 | Correct | 2 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 204 KB | Output is correct |
5 | Correct | 3 ms | 204 KB | Output is correct |
6 | Correct | 4 ms | 204 KB | Output is correct |
7 | Correct | 4 ms | 320 KB | Output is correct |
8 | Correct | 4 ms | 204 KB | Output is correct |
9 | Incorrect | 6 ms | 204 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4083 ms | 4712 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 4 ms | 304 KB | Output is correct |
3 | Correct | 2 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 204 KB | Output is correct |
5 | Correct | 3 ms | 204 KB | Output is correct |
6 | Correct | 4 ms | 204 KB | Output is correct |
7 | Correct | 4 ms | 320 KB | Output is correct |
8 | Correct | 4 ms | 204 KB | Output is correct |
9 | Incorrect | 6 ms | 204 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |