oj.uz

Submission #1118754

# Submission time Handle Problem Language Result Execution time Memory
1118754 2024-11-26T05:41:44 Z Math4Life2020 Triple Jump (JOI19_jumps) C++17
27 / 100
 238 ms 89992 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

ll N,Q; const ll Nm = 524288; const ll E = 19;
const ll INF = 2e18;
ll rmqV[Nm][E+1];
vector<ll> A,L,R;

ll l2(ll x) {
	return (31-__builtin_clz(x));
}

void initRMQ() {
	for (ll i=0;i<N;i++) {
		rmqV[i][0]=A[i];
	}
	for (ll j=1;j<=E;j++) {
		for (ll i=0;i<=(Nm-(1LL<<j));i++) { //i=Nm-2^j means Nm-2^j to Nm-2^(j-1)-1 and Nm-2^(j-1) to Nm-1
			rmqV[i][j]=max(rmqV[i][j-1],rmqV[i+(1LL<<(j-1))][j-1]);
		} 
	}
}

ll rmq(ll a, ll b) {
	if (b<a) {
		return (-INF);
	}
	ll l = l2(b-a+1);
	return max(rmqV[a][l],rmqV[b-(1LL<<l)+1][l]);
}

void solve3() {
	ll ans = -INF;
	vector<pii> vat;
	for (ll i=0;i<N;i++) {
		vat.push_back({A[i],i});
	}
	sort(vat.rbegin(),vat.rend());
	for (ll k=0;k<min(30LL,N);k++) {
		ll i = vat[k].second;
		ll vi = A[i];
		//c=i
		for (ll b=0;b<i;b++) {
			ans = max(ans,vi+A[b]+rmq(max(0LL,2*b-i),b-1));
		}
		//b=i
		for (ll a=0;a<i;a++) {
			ans = max(ans,vi+A[a]+rmq(2*i-a,N-1));
		}
		//a=i
		for (ll b=(i+1);b<N;b++) {
			ans = max(ans,vi+A[b]+rmq(2*b-i,N-1));
		}
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N;
	for (ll i=0;i<N;i++) {
		ll a1; cin >> a1;
		A.push_back(a1);
	}
	initRMQ();
	cin >> Q;
	for (ll i=0;i<Q;i++) {
		ll l1,r1; cin >> l1 >> r1;
		l1--; r1--;
		L.push_back(l1);
		R.push_back(r1);
	}
	if (Q==1 && L[0]==0 && R[0]==(N-1)) {
		solve3();
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 82352 KB Output is correct
2 Incorrect 120 ms 82460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 82352 KB Output is correct
2 Incorrect 120 ms 82460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 89920 KB Output is correct
2 Correct 186 ms 89660 KB Output is correct
3 Correct 165 ms 89992 KB Output is correct
4 Correct 184 ms 89912 KB Output is correct
5 Correct 205 ms 89968 KB Output is correct
6 Correct 204 ms 89292 KB Output is correct
7 Correct 207 ms 89304 KB Output is correct
8 Correct 238 ms 89160 KB Output is correct
9 Correct 199 ms 89596 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 82352 KB Output is correct
2 Incorrect 120 ms 82460 KB Output isn't correct
3 Halted 0 ms 0 KB -