oj.uz

Submission #242312

# Submission time Handle Problem Language Result Execution time Memory
242312 2020-06-27T08:41:16 Z jamielim Triple Jump (JOI19_jumps) C++14
19 / 100
 1348 ms 75848 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
const int INF=2012345678;
const ll LLINF=4012345678012345678LL;
const ll MOD=1000000007; //998244353; //
const ld PI=3.1415926535898;
const ld EPS=1e-9;
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(b==0)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll expo(ll b,ll p,ll m){ll res=1; while(p){if(p&1)res=(res*b)%m; b=(b*b)%m; p>>=1;} return res;}
inline ll modinv(ll a,ll m){return expo(a,m-2,m);}

int n,q;
int arr[500005];
int dp[5005][5005];

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		if(s!=e){
			l=new node(s,m);r=new node(m+1,e);
			v=max(l->v,r->v);
		}else{
			v=arr[s];
		}
	}
	int rmq(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->rmq(x,y);
		if(x>m)return r->rmq(x,y);
		return max(l->rmq(x,m),r->rmq(m+1,y));
	}
}*root;

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&arr[i]);
	root=new node(0,5005);
	for(int i=0;i<n;i++){
		for(int j=i+2;j<n;j++){
			dp[i][j]=arr[i]+arr[j]+root->rmq(i+1,(i+j)/2);
			//printf("%d ",dp[i][j]);
		}
		//printf("\n");
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<n-i;j++){
			dp[j][j+i]=max(dp[j][j+i],max(dp[j][j+i-1],dp[j+1][j+i]));
		}
	}
	
	scanf("%d",&q);
	int l,r;
	for(int i=0;i<q;i++){
		scanf("%d%d",&l,&r);l--;r--;
		printf("%d\n",dp[l][r]);
	}
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
jumps.cpp:49:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++)scanf("%d",&arr[i]);
                      ~~~~~^~~~~~~~~~~~~~
jumps.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
jumps.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l,&r);l--;r--;
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 6 ms 1152 KB Output is correct
11 Correct 1272 ms 72972 KB Output is correct
12 Correct 1268 ms 75636 KB Output is correct
13 Correct 1258 ms 75704 KB Output is correct
14 Correct 1284 ms 75648 KB Output is correct
15 Correct 1308 ms 75848 KB Output is correct
16 Correct 1290 ms 75060 KB Output is correct
17 Correct 1312 ms 74960 KB Output is correct
18 Correct 1280 ms 75012 KB Output is correct
19 Correct 1348 ms 75576 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 6 ms 1152 KB Output is correct
11 Correct 1272 ms 72972 KB Output is correct
12 Correct 1268 ms 75636 KB Output is correct
13 Correct 1258 ms 75704 KB Output is correct
14 Correct 1284 ms 75648 KB Output is correct
15 Correct 1308 ms 75848 KB Output is correct
16 Correct 1290 ms 75060 KB Output is correct
17 Correct 1312 ms 74960 KB Output is correct
18 Correct 1280 ms 75012 KB Output is correct
19 Correct 1348 ms 75576 KB Output is correct
20 Runtime error 47 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -