제출 #1118757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118757		Math4Life2020	3단 점프 (JOI19_jumps)	C++17	32 / 100	4075 ms	95500 KiB

jumps

#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]);
}

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

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();
	// }
	for (ll q=0;q<Q;q++) {
		cout << solve3(L[q],R[q]) <<"\n";
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54