oj.uz

Submission #615401

# Submission time Handle Problem Language Result Execution time Memory
615401 2022-07-31T08:59:14 Z HediChehaidar Triple Jump (JOI19_jumps) C++17
19 / 100
 2903 ms 205740 KB 
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = 1e9 + 7;//998244353 ;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

int n;
int st[(int)2e6 + 10];
ll v[(int)2e6 + 10];
void build(int pos , int l , int r){
    if(l == r){
        st[pos] = v[l]; return;
    }
    build(2 * pos + 1 , l , (l+r) / 2 ); build(2 * pos + 2 , (l+r) / 2 + 1 , r);
    st[pos] = max(st[2 * pos + 1] , st[2 * pos + 2]);
}
int rq(int pos , int l  ,int r , int i  ,int j){
    if(i > r || j < l) return 0;
    if(i <= l && j >= r) return st[pos];
    return max(rq(2 * pos + 1 , l , (l+r) / 2 , i , j) , rq(2 * pos + 2 , (l+r) / 2 + 1 , r , i, j ));
}
ll dp[5050][5050];
ll solve(int l  ,int r){
    if(r - l == 2) return v[l] + v[r] + v[l + 1];
    if(dp[l][r] != -1) return dp[l][r];
    ll ans = v[l] + v[r] + rq(0 , 0 , n - 1 , l + 1 , l + (r - l) / 2);
    return dp[l][r] = max(ans , max(solve(l + 1 , r) , solve(l , r - 1)));
}

int main(){
    //ifstream fin ("testing.txt");
    //ofstream fout ("output.txt");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    if(n > 5000) return 0;
    for(int i = 0 ; i < n ; i++) cin>>v[i];
    int q; cin>>q;
    build(0 , 0 , n - 1);
    memset(dp , -1 , sizeof dp);
    while(q--){
        int  l , r; cin>>l>>r; l--,r--;
        cout << solve(l , r) << "\n";
    }
    return 0;
}

/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 199916 KB Output is correct
2 Correct 89 ms 199956 KB Output is correct
3 Correct 75 ms 199976 KB Output is correct
4 Correct 88 ms 199880 KB Output is correct
5 Correct 74 ms 199880 KB Output is correct
6 Correct 83 ms 199832 KB Output is correct
7 Correct 77 ms 199920 KB Output is correct
8 Correct 87 ms 199864 KB Output is correct
9 Correct 75 ms 199972 KB Output is correct
10 Correct 74 ms 199876 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 199916 KB Output is correct
2 Correct 89 ms 199956 KB Output is correct
3 Correct 75 ms 199976 KB Output is correct
4 Correct 88 ms 199880 KB Output is correct
5 Correct 74 ms 199880 KB Output is correct
6 Correct 83 ms 199832 KB Output is correct
7 Correct 77 ms 199920 KB Output is correct
8 Correct 87 ms 199864 KB Output is correct
9 Correct 75 ms 199972 KB Output is correct
10 Correct 74 ms 199876 KB Output is correct
11 Correct 2595 ms 205736 KB Output is correct
12 Correct 2556 ms 205700 KB Output is correct
13 Correct 2605 ms 205632 KB Output is correct
14 Correct 2473 ms 205736 KB Output is correct
15 Correct 2534 ms 205740 KB Output is correct
16 Correct 2550 ms 205068 KB Output is correct
17 Correct 2903 ms 205048 KB Output is correct
18 Correct 2741 ms 205088 KB Output is correct
19 Correct 2827 ms 205604 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 199916 KB Output is correct
2 Correct 89 ms 199956 KB Output is correct
3 Correct 75 ms 199976 KB Output is correct
4 Correct 88 ms 199880 KB Output is correct
5 Correct 74 ms 199880 KB Output is correct
6 Correct 83 ms 199832 KB Output is correct
7 Correct 77 ms 199920 KB Output is correct
8 Correct 87 ms 199864 KB Output is correct
9 Correct 75 ms 199972 KB Output is correct
10 Correct 74 ms 199876 KB Output is correct
11 Correct 2595 ms 205736 KB Output is correct
12 Correct 2556 ms 205700 KB Output is correct
13 Correct 2605 ms 205632 KB Output is correct
14 Correct 2473 ms 205736 KB Output is correct
15 Correct 2534 ms 205740 KB Output is correct
16 Correct 2550 ms 205068 KB Output is correct
17 Correct 2903 ms 205048 KB Output is correct
18 Correct 2741 ms 205088 KB Output is correct
19 Correct 2827 ms 205604 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -