oj.uz

답안 #1118761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1118761 2024-11-26T05:49:48 Z Math4Life2020 3단 점프 (JOI19_jumps) C++17
32 / 100
 4000 ms 95504 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,sse4")
#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(20LL,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);
	}
	for (ll q=0;q<Q;q++) {
		cout << solve3(L[q],R[q]) <<"\n";
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 82516 KB Output is correct
2 Correct 109 ms 82484 KB Output is correct
3 Correct 105 ms 82448 KB Output is correct
4 Correct 114 ms 82504 KB Output is correct
5 Correct 101 ms 82292 KB Output is correct
6 Correct 129 ms 82516 KB Output is correct
7 Correct 120 ms 82504 KB Output is correct
8 Correct 105 ms 82432 KB Output is correct
9 Correct 132 ms 82300 KB Output is correct
10 Correct 109 ms 82516 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 82516 KB Output is correct
2 Correct 109 ms 82484 KB Output is correct
3 Correct 105 ms 82448 KB Output is correct
4 Correct 114 ms 82504 KB Output is correct
5 Correct 101 ms 82292 KB Output is correct
6 Correct 129 ms 82516 KB Output is correct
7 Correct 120 ms 82504 KB Output is correct
8 Correct 105 ms 82432 KB Output is correct
9 Correct 132 ms 82300 KB Output is correct
10 Correct 109 ms 82516 KB Output is correct
11 Execution timed out 4069 ms 95504 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 89908 KB Output is correct
2 Correct 155 ms 89936 KB Output is correct
3 Correct 148 ms 89952 KB Output is correct
4 Correct 191 ms 89940 KB Output is correct
5 Correct 179 ms 89952 KB Output is correct
6 Correct 178 ms 89360 KB Output is correct
7 Correct 184 ms 89100 KB Output is correct
8 Correct 187 ms 89252 KB Output is correct
9 Correct 172 ms 89616 KB Output is correct

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 82516 KB Output is correct
2 Correct 109 ms 82484 KB Output is correct
3 Correct 105 ms 82448 KB Output is correct
4 Correct 114 ms 82504 KB Output is correct
5 Correct 101 ms 82292 KB Output is correct
6 Correct 129 ms 82516 KB Output is correct
7 Correct 120 ms 82504 KB Output is correct
8 Correct 105 ms 82432 KB Output is correct
9 Correct 132 ms 82300 KB Output is correct
10 Correct 109 ms 82516 KB Output is correct
11 Execution timed out 4069 ms 95504 KB Time limit exceeded
12 Halted 0 ms 0 KB -