oj.uz

Submission #282469

# Submission time Handle Problem Language Result Execution time Memory
282469 2020-08-24T12:49:15 Z aloo123 Triple Jump (JOI19_jumps) C++14
19 / 100
 3446 ms 127572 KB 
        #include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(5000+5); // TODO : change value as per problem
const ll MOD = 1e9+7;

int a[N];
int ans[N][N];
int t[4*N];
void build(int node,int l,int r){
    if(l == r){
        t[node] = a[l];
    }
    else{
        int m = (l+r)>>1ll;
        build(node*2,l,m);
        build(node*2+1,m+1,r);
        t[node] = max(t[node*2],t[node*2+1]);
    }
}
int query(int node,int l,int r,int st,int en){
    if(l > en || r < st) return 0;
    if(l >= st && r <= en) return t[node];
    int m = (l+r)>>1ll;
    int p1 = query(node*2,l,m,st,en);
    int p2 = query(node*2+1,m+1,r,st,en);
    return max(p1,p2);
}

void solve(){
    int n;
    cin >> n;
    for(int i =1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int sz = 3;sz<=n;sz++){
        for(int l = 1;(l+sz-1)<=n;l++){
            int r = (l+sz-1);
            // b <= (a + c)/2
            int k = (l+r)>>1ll;
            ans[l][r] = max(max(ans[l+1][r],ans[l][r-1]), a[l] + a[r] + query(1,1,n,l+1,k));
        }   
    }
    int q;
    cin >> q;
    while(q--){
        int i,j;
        cin >> i >> j;
        cout << ans[i][j] << endl;
    }
}
signed main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 3383 ms 127572 KB Output is correct
12 Correct 3376 ms 127308 KB Output is correct
13 Correct 3395 ms 127232 KB Output is correct
14 Correct 3446 ms 127436 KB Output is correct
15 Correct 3386 ms 127256 KB Output is correct
16 Correct 3357 ms 126600 KB Output is correct
17 Correct 3377 ms 126456 KB Output is correct
18 Correct 3340 ms 126580 KB Output is correct
19 Correct 3437 ms 127096 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 1152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 3383 ms 127572 KB Output is correct
12 Correct 3376 ms 127308 KB Output is correct
13 Correct 3395 ms 127232 KB Output is correct
14 Correct 3446 ms 127436 KB Output is correct
15 Correct 3386 ms 127256 KB Output is correct
16 Correct 3357 ms 126600 KB Output is correct
17 Correct 3377 ms 126456 KB Output is correct
18 Correct 3340 ms 126580 KB Output is correct
19 Correct 3437 ms 127096 KB Output is correct
20 Runtime error 14 ms 1152 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -