제출 #8077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8077		gs13068	휴가 (IOI14_holiday)	C++98	0 / 100	24 ms	23624 KiB

holiday

#include"holiday.h"
#include<algorithm>

std::pair<int,int> b[100000];
int c[100000];
long long l[200000];
long long r[200000];

struct rec
{
	int s;
	int e;
	int l;
	int r;
} q[1000000];
int qn;

long long sum[200001];
int cnt[200001];

long long findMaxAttraction(int n,int m,int d,int a[])
{
	long long te;
	int i,j,k,p,t,cut;
	for(i=0;i<n;i++)
	{
		b[i].first=a[i];
		b[i].second=i;
	}
	for(i=1;i<=200000;i++)sum[i+1]=cnt[i+1]=0;
    std::sort(b,b+n);
    for(i=0;i<n;i++)c[b[i].second]=i+1;
	qn=0;
    q[qn].s=1;
    q[qn].e=(n-d)*2-1;
    q[qn].l=d;
    q[qn].r=n-1;
    qn++;
    j=d-1;
    for(i=0;i<qn;i++)if(q[i].s<=q[i].e)
	{
		p=(q[i].s+q[i].e)/2;
		while(j<q[i].l)
		{
			j++;
			k=c[j];
            while(k<=200000)
			{
				sum[k]+=a[j];
                cnt[k]++;
                k+=k&-k;
			}
		}
		while(j>q[i].l)
		{
			k=c[j];
            while(k<=200000)
			{
				sum[k]-=a[j];
                cnt[k]--;
                k+=k&-k;
			}
			j--;
		}
		k=0;
		for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=2*d-j)k|=1<<t;
        while(k)
		{
			l[p]+=sum[k];
			k-=k&-k;
		}
		cut=j;
		while(j<q[i].r)
		{
			j++;
			k=c[j];
            while(k<=200000)
			{
				sum[k]+=a[j];
                cnt[k]++;
                k+=k&-k;
			}
			k=0;
			for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=2*d-j)k|=1<<t;
			te=0;
			while(k)
			{
				te+=sum[k];
				k-=k&-k;
			}
			if(te>l[p])
			{
				l[p]=te;
				cut=j;
			}
		}
		q[qn].s=q[i].s;
		q[qn].e=p-1;
		q[qn].l=q[i].l;
        q[qn].r=cut;
        qn++;
		q[qn].s=p+1;
		q[qn].e=q[i].e;
		q[qn].l=cut;
        q[qn].r=q[i].r;
        qn++;
	}
	return r[d];
}

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