oj.uz

Submission #681688

# Submission time Handle Problem Language Result Execution time Memory
681688 2023-01-13T17:24:01 Z edogawa_something Triple Jump (JOI19_jumps) C++17
19 / 100
 3044 ms 148172 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;  
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string st;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define pu push
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(ll i=0;i<n;i++)
#define forx(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define pob pop_back
#define all(v) v.begin(),v.end()  
#define lb lower_bound
#define ub upper_bound
#define pof pop_front
#define pow powww
#define prtll(x) printf("%lld",x)
#define prtld(x) printf("%Lf",x)
#define prtst(x) printf("%s",x)
#define prtch(x) printf("%c",x)
#define measure chrono::high_resolution_clock::now()
const ll dx[]{1,0,-1,0};
const ll dy[]{0,-1,0,1};
const ll inf=2e18;
//const ll mod=1e9+7;
const ll LM=1e7+2;
const ll M=3e5+10;
const ll MM=5002;
const ll MMM=101;
const ld pi=acos(-1);
const ll mod=998244353;
ll pow(ll r,ll to,ll m=mod){
  ll res=1;
  while(to){
    if((to&1))
    res*=r,res%=m;
    r*=r,r%=m;
    to=(to>>1);
  } 
  return res;
}
struct seg{
  ll sz=1;
  vii mx;
  void init(ll x){
    while(sz<x)
    sz=(sz<<1);
    mx.resize((sz<<1));
  }
  void update(ll i,ll v,ll x,ll lx,ll rx){
    if(rx-lx==1){
      mx[x]=v;
      return;
    }
    ll mid=((lx+rx)>>1);
    if(i<mid)
    update(i,v,x*2+1,lx,mid);
    else
    update(i,v,x*2+2,mid,rx);
    mx[x]=max(mx[x*2+1],mx[x*2+2]);
  }
  ll query(ll l,ll r,ll x,ll lx,ll rx){
    if(rx<=r&&lx>=l)
    return mx[x];
    else if(rx<=l||lx>=r)
    return 0;
    else{
    ll mid=((lx+rx)>>1);
    return max(query(l,r,x*2+1,lx,mid),query(l,r,x*2+2,mid,rx));
    }
  }
};
ll n,a[M],dp[MM][MM];
seg s;
ll DP(ll l,ll r){
  if(r-l<=1)
  return 0;
  if(dp[l][r]>0)
  return dp[l][r];
  dp[l][r]=max(DP(l+1,r),DP(l,r-1));
  dp[l][r]=max(dp[l][r],a[l]+a[r]+s.query(l+1,((l+r+2)>>1),0,0,s.sz));
  return dp[l][r];
}
int main(){
  cin>>n;
  s.init(n);
  forn(i,n)
  cin>>a[i],s.update(i,a[i],0,0,s.sz);
  test{
    ll l,r;
    cin>>l>>r;
    l--,r--;
    cout<<DP(l,r)<<'\n';
  }
  return 0; 
}
/*

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 696 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 692 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 696 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 692 KB Output is correct
11 Correct 2787 ms 127688 KB Output is correct
12 Correct 2783 ms 127648 KB Output is correct
13 Correct 2992 ms 127600 KB Output is correct
14 Correct 3044 ms 127672 KB Output is correct
15 Correct 2765 ms 127612 KB Output is correct
16 Correct 2762 ms 126908 KB Output is correct
17 Correct 2834 ms 127112 KB Output is correct
18 Correct 2810 ms 126976 KB Output is correct
19 Correct 2832 ms 127564 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 696 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 692 KB Output is correct
11 Correct 2787 ms 127688 KB Output is correct
12 Correct 2783 ms 127648 KB Output is correct
13 Correct 2992 ms 127600 KB Output is correct
14 Correct 3044 ms 127672 KB Output is correct
15 Correct 2765 ms 127612 KB Output is correct
16 Correct 2762 ms 126908 KB Output is correct
17 Correct 2834 ms 127112 KB Output is correct
18 Correct 2810 ms 126976 KB Output is correct
19 Correct 2832 ms 127564 KB Output is correct
20 Incorrect 2516 ms 148172 KB Output isn't correct
21 Halted 0 ms 0 KB -