# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
885225 | 2023-12-09T10:05:42 Z | rukashii | Triple Jump (JOI19_jumps) | C++17 | 373 ms | 177748 KB |
#include <bits/stdc++.h> using namespace std; #define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } // #define int long long #define f first #define s second void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { if (s.size()) setIn(s+".inp"), setOut(s+".out"); } const int maxn = 5e5 + 2; int a[maxn], n, q; namespace Sub1 { void solve() { while (q--) { int l, r, ans = 0; cin >> l >> r; for (int i = l; i <= r; i++) { for (int j = i + 1; j <= r; j++) { for (int k = j + 1; k <= r; k++) { if (k - j >= j - i) { ans = max(ans, a[i] + a[j] + a[k]); } } } } cout << ans << '\n'; } } } // namespace Sub1 namespace Sub2 { const int s2maxn = 5002; int dp[s2maxn][s2maxn], mx[s2maxn][s2maxn]; void solve() { for (int i = 1; i <= n; i++) { mx[i][i] = a[i]; } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { mx[i][j] = max(mx[i][j - 1], a[j]); } } for (int sz = 3; sz <= n; sz++) { for (int i = 1; i + sz - 1 <= n; i++) { int l = i, r = i + sz - 1; // if (sz == 3 && i == 1) // cout << l << ' ' << r << ' ' << (l + r) / 2 << ' ' << mx[l][(l + r) / 2] << '\n'; dp[l][r] = max({dp[l + 1][r], dp[l][r - 1], a[l] + a[r] + mx[l + 1][(l + r) / 2]}); } } while (q--) { int l, r; cin >> l >> r; cout << dp[l][r] << '\n'; } } } // namespace Sub2 namespace Sub3 { int prf[maxn]; void solve() { stack <int> st; for (int i = 1; i <= n; i++) { while (st.size() && a[st.top()] < a[i]) { if (i + (i - st.top() + 1) - 1 <= n) prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]); st.pop(); } if (st.size()) if (i + (i - st.top() + 1) - 1 <= n) prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]); st.push(i); } for (int i = 1; i <= n; i++) { prf[i] = max(prf[i - 1], prf[i]); } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, prf[i] + a[i]); } cout << ans << '\n'; } } // namespace Sub3 signed main() { // setIO(); file; ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; cin >> q; if (n <= 100) { return Sub1::solve(), 0; } if (n <= 5000) { return Sub2::solve(), 0; } if (q == 1) { return Sub3::solve(), 0; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 2512 KB | Output is correct |
3 | Correct | 3 ms | 2396 KB | Output is correct |
4 | Correct | 3 ms | 2392 KB | Output is correct |
5 | Correct | 3 ms | 2396 KB | Output is correct |
6 | Correct | 3 ms | 2396 KB | Output is correct |
7 | Correct | 3 ms | 2396 KB | Output is correct |
8 | Correct | 3 ms | 2396 KB | Output is correct |
9 | Correct | 4 ms | 2396 KB | Output is correct |
10 | Correct | 3 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 2512 KB | Output is correct |
3 | Correct | 3 ms | 2396 KB | Output is correct |
4 | Correct | 3 ms | 2392 KB | Output is correct |
5 | Correct | 3 ms | 2396 KB | Output is correct |
6 | Correct | 3 ms | 2396 KB | Output is correct |
7 | Correct | 3 ms | 2396 KB | Output is correct |
8 | Correct | 3 ms | 2396 KB | Output is correct |
9 | Correct | 4 ms | 2396 KB | Output is correct |
10 | Correct | 3 ms | 2396 KB | Output is correct |
11 | Correct | 356 ms | 177744 KB | Output is correct |
12 | Correct | 361 ms | 177748 KB | Output is correct |
13 | Correct | 344 ms | 177744 KB | Output is correct |
14 | Correct | 355 ms | 177704 KB | Output is correct |
15 | Correct | 361 ms | 177688 KB | Output is correct |
16 | Correct | 347 ms | 177088 KB | Output is correct |
17 | Correct | 341 ms | 177424 KB | Output is correct |
18 | Correct | 373 ms | 177132 KB | Output is correct |
19 | Correct | 357 ms | 177648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 4800 KB | Output is correct |
2 | Correct | 19 ms | 4944 KB | Output is correct |
3 | Correct | 17 ms | 5808 KB | Output is correct |
4 | Correct | 19 ms | 4936 KB | Output is correct |
5 | Correct | 20 ms | 4924 KB | Output is correct |
6 | Correct | 16 ms | 4188 KB | Output is correct |
7 | Correct | 15 ms | 4180 KB | Output is correct |
8 | Correct | 15 ms | 4272 KB | Output is correct |
9 | Correct | 16 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 2512 KB | Output is correct |
3 | Correct | 3 ms | 2396 KB | Output is correct |
4 | Correct | 3 ms | 2392 KB | Output is correct |
5 | Correct | 3 ms | 2396 KB | Output is correct |
6 | Correct | 3 ms | 2396 KB | Output is correct |
7 | Correct | 3 ms | 2396 KB | Output is correct |
8 | Correct | 3 ms | 2396 KB | Output is correct |
9 | Correct | 4 ms | 2396 KB | Output is correct |
10 | Correct | 3 ms | 2396 KB | Output is correct |
11 | Correct | 356 ms | 177744 KB | Output is correct |
12 | Correct | 361 ms | 177748 KB | Output is correct |
13 | Correct | 344 ms | 177744 KB | Output is correct |
14 | Correct | 355 ms | 177704 KB | Output is correct |
15 | Correct | 361 ms | 177688 KB | Output is correct |
16 | Correct | 347 ms | 177088 KB | Output is correct |
17 | Correct | 341 ms | 177424 KB | Output is correct |
18 | Correct | 373 ms | 177132 KB | Output is correct |
19 | Correct | 357 ms | 177648 KB | Output is correct |
20 | Correct | 21 ms | 4800 KB | Output is correct |
21 | Correct | 19 ms | 4944 KB | Output is correct |
22 | Correct | 17 ms | 5808 KB | Output is correct |
23 | Correct | 19 ms | 4936 KB | Output is correct |
24 | Correct | 20 ms | 4924 KB | Output is correct |
25 | Correct | 16 ms | 4188 KB | Output is correct |
26 | Correct | 15 ms | 4180 KB | Output is correct |
27 | Correct | 15 ms | 4272 KB | Output is correct |
28 | Correct | 16 ms | 4444 KB | Output is correct |
29 | Incorrect | 36 ms | 7472 KB | Output isn't correct |
30 | Halted | 0 ms | 0 KB | - |