Submission #289958

#	Time	Username	Problem	Language	Result	Execution time	Memory
289958		shayan_p	휴가 (IOI14_holiday)	C++17	17 / 100	5059 ms	5216 KiB

holiday

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include"holiday.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
#define data STRANGE

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int cost[maxn], tmp[maxn], idcost[maxn];
int A[maxn], B[maxn];
ll ANS1[2 * maxn], ANS2[2 * maxn];

struct Data{
    multiset<int> ms;
    void add(int id){
	ms.insert(-cost[id]);
    }
    void era(int id){
	ms.erase(ms.find(-cost[id]));
    }
    void clear(){
	ms.clear();
    }
    ll ask(int n){
	ll ans = 0;
	for(auto x : ms){
	    if(n == 0)
		break;
	    ans+= x;
	    n--;
	}
	return -ans;
    }    
};
Data data;

void divide(int l, int r, int L, int R, int *cst, ll *ret, int stp){
    if(l > r){
	while(L < R){
	    data.add(cst[L]);
	    L++;
	}
	return;
    }
    int mid = (l+r) >> 1;
    pli bst = {-1, -1};
    int pos = L;
    while(pos <= R && stp * pos <= mid){
	data.add(cst[pos]);
	bst = max(bst, (pli){ data.ask(mid - stp * pos), pos });
	pos++;
    }
    while(pos > L){
	--pos;
	data.era(cst[pos]);	
    }
    ret[mid] = bst.F;
    divide(l, mid-1, L, bst.S, cst, ret, stp);
    divide(mid+1, r, bst.S, R, cst, ret, stp);
}
ll solve(int n, int start, int d, int a[]){
    int n1 = start, n2 = n-n1;
    for(int i = start; i < n; i++)
	A[i-start] = a[i];
    for(int i = start-1; i >= 0; i--)
	B[start-i-1] = a[i];
    divide(0, 2 * n1 - 1, 0, n1 - 1, B, ANS1, 2);
    data.clear();
    divide(0, 2 * n2 - 1, 0, n2 - 1, A, ANS2, 1);
    data.clear();
    ll ans = ANS2[min(2 * n2-1, d)];
    for(int i = 0; i < 2 * n1 && 2 + i <= d; i++){
	ans = max(ans, ANS1[i] + ANS2[min(2 * n2 -1, d-i-2)]);
    }
    return ans;
}
ll findMaxAttraction(int n, int start, int d, int a[]){
    for(int i = 0; i < n; i++){
	cost[i] = a[i];
	a[i] = i;
	tmp[i] = i;
    }
    sort(tmp, tmp + n, [](int i, int j){ return cost[i] < cost[j]; } );
    for(int i = 0; i < n; i++){
	idcost[ tmp[i] ] = i;
    }
    
    ll ans = solve(n, start, d, a);
    reverse(a, a + n);
    ans = max(ans, solve(n, n-1-start, d, a));
    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53