oj.uz

Submission #234293

# Submission time Handle Problem Language Result Execution time Memory
234293 2020-05-23T19:52:06 Z Knps4422 Triple Jump (JOI19_jumps) C++14
19 / 100
 730 ms 244148 KB 
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/

#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
#define x real
#define y imag

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef complex<int> point;
const int nmax = 5005, mmax = 80;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = INT_MAX;

int n, q;
ll a[nmax];
int l , r;
ll maxrange[nmax][nmax], dp[nmax][nmax];



int main(){
	fast;
	cin >> n;
	forn(i,n)cin >> a[i];
	for(int i = 1; i <= n; i ++){
		for(int j = i ; j <= n ; j++){
			maxrange[i][j] = max(maxrange[i][j-1],a[j]);
		}
	}
	for(int lenght = 2 ; lenght <= n ; lenght ++){
		for(int i = 1; i <= n ; i++){
			l = i , r = i + lenght;
			if(r > n)continue;
			int mid = (l + r)/2;
			dp[l][r] = max(dp[l][r-1] , dp[l+1][r]);
			dp[l][r] = max(dp[l][r] , a[l] + a[r] + maxrange[l+1][mid]);
		}
	}
	cin >> q;
	forn(ss,q){
		cin >> l >> r;
		cout << dp[l][r] << '\n';	
	}
	
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 730 ms 244076 KB Output is correct
12 Correct 705 ms 244048 KB Output is correct
13 Correct 690 ms 244096 KB Output is correct
14 Correct 693 ms 244148 KB Output is correct
15 Correct 685 ms 244084 KB Output is correct
16 Correct 708 ms 243444 KB Output is correct
17 Correct 711 ms 243344 KB Output is correct
18 Correct 706 ms 243360 KB Output is correct
19 Correct 690 ms 243960 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 640 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 4 ms 384 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 730 ms 244076 KB Output is correct
12 Correct 705 ms 244048 KB Output is correct
13 Correct 690 ms 244096 KB Output is correct
14 Correct 693 ms 244148 KB Output is correct
15 Correct 685 ms 244084 KB Output is correct
16 Correct 708 ms 243444 KB Output is correct
17 Correct 711 ms 243344 KB Output is correct
18 Correct 706 ms 243360 KB Output is correct
19 Correct 690 ms 243960 KB Output is correct
20 Runtime error 21 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -