oj.uz

Submission #1009668

# Submission time Handle Problem Language Result Execution time Memory
1009668 2024-06-27T19:21:10 Z MarwenElarbi Triple Jump (JOI19_jumps) C++17
19 / 100
 729 ms 524288 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e3+5;
signed main(){
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int tab[n];
    int dp[n][n];
    memset(dp,0,sizeof dp);
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i];
    }
    for (int i = n-3; i >= 0; i--)
    {
        int mx=tab[i+1];
        for (int j = i+2; j < n; ++j)
        {
            dp[i][j]=max(dp[i][j],max(dp[i+1][j],dp[i][j-1]));
            dp[i][j]=max(dp[i][j],tab[i]+tab[j]+mx);
            //cout <<i<<" "<<j<<" "<<dp[i][j]<<endl;
            mx=max(mx,tab[i+(j-i+1)/2]);
        }
    }
    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        x--;y--;
        cout <<dp[x][y]<<endl;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 700 ms 107880 KB Output is correct
12 Correct 718 ms 107884 KB Output is correct
13 Correct 691 ms 107856 KB Output is correct
14 Correct 701 ms 107884 KB Output is correct
15 Correct 668 ms 107812 KB Output is correct
16 Correct 729 ms 107180 KB Output is correct
17 Correct 720 ms 107112 KB Output is correct
18 Correct 691 ms 107272 KB Output is correct
19 Correct 680 ms 107832 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 700 ms 107880 KB Output is correct
12 Correct 718 ms 107884 KB Output is correct
13 Correct 691 ms 107856 KB Output is correct
14 Correct 701 ms 107884 KB Output is correct
15 Correct 668 ms 107812 KB Output is correct
16 Correct 729 ms 107180 KB Output is correct
17 Correct 720 ms 107112 KB Output is correct
18 Correct 691 ms 107272 KB Output is correct
19 Correct 680 ms 107832 KB Output is correct
20 Runtime error 236 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -