oj.uz

Submission #742595

# Submission time Handle Problem Language Result Execution time Memory
742595 2023-05-16T14:51:13 Z myrcella Triple Jump (JOI19_jumps) C++17
19 / 100
 517 ms 289216 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 5e3+10;

int n;
int a[maxn];
int dp[maxn][maxn],ans[maxn][maxn];
int mx[maxn][maxn];

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	rep(i,1,n+1) cin>>a[i];
	rep(i,1,n+1) {
		mx[i][0] = 0;
		for (int j=1;i-j-j>0;j++) mx[i][j] = max(mx[i][j-1], a[i]+a[i-j]+a[i-j-j]);
	}
	rep(i,1,n-1) {
		ans[i][i+2] = dp[i][i+2] = a[i]+a[i+1]+a[i+2];
		rep(j,i+3,n+1) {
			dp[i][j] = dp[i][j-1] + a[j] - a[j-1];
			dp[i][j] = max(dp[i][j],mx[j][(j-i)/2]);
			ans[i][j] = max(ans[i][j-1],dp[i][j]);
		}
	}
	int _;cin>>_;
	while (_--) {
		int x,y;cin>>x>>y;
		cout<<ans[x][y]<<"\n";
	}	
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1480 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 383 ms 188544 KB Output is correct
12 Correct 367 ms 188492 KB Output is correct
13 Correct 356 ms 188620 KB Output is correct
14 Correct 402 ms 188620 KB Output is correct
15 Correct 364 ms 188596 KB Output is correct
16 Correct 373 ms 187812 KB Output is correct
17 Correct 367 ms 187944 KB Output is correct
18 Correct 370 ms 187884 KB Output is correct
19 Correct 372 ms 188428 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 517 ms 289216 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 1 ms 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1480 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 383 ms 188544 KB Output is correct
12 Correct 367 ms 188492 KB Output is correct
13 Correct 356 ms 188620 KB Output is correct
14 Correct 402 ms 188620 KB Output is correct
15 Correct 364 ms 188596 KB Output is correct
16 Correct 373 ms 187812 KB Output is correct
17 Correct 367 ms 187944 KB Output is correct
18 Correct 370 ms 187884 KB Output is correct
19 Correct 372 ms 188428 KB Output is correct
20 Runtime error 517 ms 289216 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -