oj.uz

Submission #286033

# Submission time Handle Problem Language Result Execution time Memory
286033 2020-08-30T01:24:18 Z emanIaicepsa Holiday (IOI14_holiday) C++14
24 / 100
 136 ms 65540 KB 
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define fi first
#define se second
#define pii pair<ll,ll>
#define all(n) (n).begin(),(n).end()
#define pb push_back
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';

struct Persistent_tree{
	ll l, r;
	ll tot, cnt;
}tr[8000005];
ll idx = 0, rt[100005];

void insert(ll copy, ll &now, ll val, ll L, ll R){
	now = ++idx;
	if(copy) tr[now] = tr[copy];
	tr[now].cnt++;
	tr[now].tot += val;
	if(L == R) return;
	ll M = (L+R)/2;
	if(val <= M) insert(tr[copy].l, tr[now].l, val, L, M);
	else insert(tr[copy].r, tr[now].r, val, M+1, R);
}

ll query(int lid, int rid, int num){
	if(tr[rid].cnt - tr[lid].cnt <= num) return tr[rid].tot - tr[lid].tot;
	if(num <= 0) return 0;
	int Rr = tr[rid].r, Rl = tr[rid].l, Lr = tr[lid].r, Ll = tr[lid].l;
	if(tr[Rr].cnt - tr[Lr].cnt <= num){
		num -= tr[Rr].cnt - tr[Lr].cnt;
		return tr[Rr].tot - tr[Lr].tot + query(Ll, Rl, num);
	}
	else return query(Lr, Rr, num);
}

ll solve(int n, int s, int d, int arr[]){
	ll ans = 0;
	for(int i=1;i<=idx;i++) tr[i].l = tr[i].r = tr[i].tot = tr[i].cnt = 0;
	idx = 1;
	rt[0] = 1;
	
	if(s == 1) return -1;
	for(int i=1;i<=n;i++) insert(rt[i-1], rt[i], arr[i], 0, 1000000000);

	for(int i=1;i<=s;i++){
		if(d <= s-i) continue;
		ll tans = query(rt[i-1], rt[s], d - (s-i));
		
		for(int j=s+1;j<=n;j++){
			ll left = d - (s-i) - (j-i);
			if(left <= 0) break;
			ll que = query(rt[i-1], rt[j], left);
			tans = max(tans, que);
		}
		ans = max(ans, tans);
	}
	return ans;
}

int arr[100005];
ll findMaxAttraction(int n, int start, int d, int in[]) {
	start++;
	for(int i=1;i<=n;i++) arr[i] = in[i-1];
	ll al = solve(n, start, d, arr);
	reverse(arr+1, arr+1+n);
	start = n + 1 - start;
	ll ar = solve(n, start, d, arr);
	return max(al, ar);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB Output is correct
2 Correct 5 ms 3232 KB Output is correct
3 Correct 4 ms 3328 KB Output is correct
4 Correct 136 ms 3192 KB Output is correct
5 Correct 75 ms 2816 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 16 ms 1280 KB Output is correct
8 Correct 15 ms 1280 KB Output is correct
9 Correct 15 ms 1400 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -