oj.uz

Submission #1013003

# Submission time Handle Problem Language Result Execution time Memory
1013003 2024-07-03T04:43:12 Z ReLice Triple Jump (JOI19_jumps) C++14
19 / 100
 231 ms 107604 KB 
#include <bits/stdc++.h>
#define ll unsigned int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e9;
const ll mod=998244353;
const ll N=5e3+7;
const ld eps=1e-9;
ll dp[N][N];
ll sparse[N][20];
ll a[N];
ll get(ll l,ll r){
    ll x=0;
    for(ll i=0;i<20;i++){
        if((1ll<<i)>r-l+1)break;
        x=i;
    }
    r=r-(1ll<<x)+1;
    return max(sparse[l][x],sparse[r][x]);
}
void solve(){
    ll i,j;
    ll n,q;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        if(i>2) dp[i-2][i]=a[i-2]+a[i-1]+a[i];
    }
    for(i=0;i<20;i++)sparse[n][i]=a[n];
    for(i=n-1;i>0;i--){
        sparse[i][0]=a[i];
        for(j=1;j<20;j++){
            if((1ll<<j-1)+i>n)break;
            sparse[i][j]=max(sparse[i][j-1],sparse[i+(1ll<<j-1)][j-1]);
        }
    }
    for(ll len=3;len<n;len++){
        ll l,r;
        for(l=1;l<n;l++){
            if(l+len>n)break;
            r=l+len;
            dp[l][r]=max(dp[l+1][r],dp[l][r-1]);
            chmax(dp[l][r],a[l]+a[r]+get(l+1,(r+l)/2));
        }
    }
    cin>>q;
    for(i=0;i<q;i++){
        ll l,r;
        cin>>l>>r;
        cout<<dp[l][r]<<endl;
    }
}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*





*/

Compilation message

jumps.cpp: In function 'void solve()':
jumps.cpp:69:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |             if((1ll<<j-1)+i>n)break;
      |                      ~^~
jumps.cpp:70:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |             sparse[i][j]=max(sparse[i][j-1],sparse[i+(1ll<<j-1)][j-1]);
      |                                                            ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 231 ms 73212 KB Output is correct
12 Correct 229 ms 75344 KB Output is correct
13 Correct 219 ms 74880 KB Output is correct
14 Correct 222 ms 75356 KB Output is correct
15 Correct 226 ms 74832 KB Output is correct
16 Correct 229 ms 74576 KB Output is correct
17 Correct 224 ms 74324 KB Output is correct
18 Correct 231 ms 74196 KB Output is correct
19 Correct 223 ms 74716 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 107604 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 2648 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 231 ms 73212 KB Output is correct
12 Correct 229 ms 75344 KB Output is correct
13 Correct 219 ms 74880 KB Output is correct
14 Correct 222 ms 75356 KB Output is correct
15 Correct 226 ms 74832 KB Output is correct
16 Correct 229 ms 74576 KB Output is correct
17 Correct 224 ms 74324 KB Output is correct
18 Correct 231 ms 74196 KB Output is correct
19 Correct 223 ms 74716 KB Output is correct
20 Runtime error 57 ms 107604 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -