| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 329458 | tnk2908 | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// main.cpp
// holiday
//
// Created by Trần Nam Khánh on 11/21/20.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const long long nax=1e5+1;
const long long inf=1e18;
struct node
{
long long s,ac;
}seg[5*nax];
void update(long long id,long long l,long long r,long long k,long long val,long long stat)
{
if(k<l||r<k)return;
if(l==r)
{
seg[id].ac=stat;
seg[id].s=val;
return;
}
long long mid=(l+r)>>1;
update(id*2,l,mid,k,val,stat);
update(id*2+1,mid+1,r,k,val,stat);
seg[id].ac=seg[id*2].ac+seg[id*2+1].ac;
seg[id].s=seg[id*2].s+seg[id*2+1].s;
}
long long query(long long id,long long l,long long r,long long x)
{
long long res=0;
if(x<0)return 0;
if(seg[id].ac<=x)
{
return seg[id].s;
}
long long mid=(l+r)>>1;
res=query(id*2,l,mid,min(x,seg[id*2].ac))+query(id*2+1,mid+1,r,x-seg[id*2].ac);
return res;
}
long long n,st,d,a[nax],pl[nax],attraction[nax];
long long dp[nax];
long long ab(long long a)
{
if(a<0)return -a;else return a;
}
void dc1(long long lo,long long hi,long long lovl,long long hivl)
{
if(lo>hi)return;
long long mid=(lo+hi)>>1,x=lovl;
for(long long i=mid;i<=st;i++)
{
update(1,1,n,pl[i],a[i],1);
}
for(long long i=lovl;i<=hivl;i++)
{
long long tmpd=d-ab(st-mid)-ab(mid-i);
if(tmpd<0)break;
update(1,1,n,pl[i],a[i],1);
long long tmp=query(1,1,n,tmpd);
if(dp[mid]<tmp)
{
dp[mid]=tmp;
x=i;
}
}
for(long long i=mid;i<=st;i++)
{
update(1,1,n,pl[i],0,0);
}
for(long long i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
dc1(mid+1,hi,x,hivl);
for(long long i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
dc1(lo,mid-1,lovl,x);
}
void dc2(long long lo,long long hi,long long lovl,long long hivl)
{
if(lo>hi)return;
long long mid=(lo+hi)>>1,x=lovl;
for(long long i=st;i<=mid;i++)
{
update(1,1,n,pl[i],a[i],1);
}
for(long long i=hivl;i>=lovl;i--)
{
long long tmpd=d-ab(st-mid)-ab(mid-i);
if(tmpd<0)break;
update(1,1,n,pl[i],a[i],1);
long long tmp=query(1,1,n,tmpd);
if(dp[mid]<tmp)
{
dp[mid]=tmp;
x=i;
}
}
for(long long i=st;i<=mid;i++)
{
update(1,1,n,pl[i],0,0);
}
for(long long i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
dc2(lo,mid-1,lovl,x);
for(long long i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
dc2(mid+1,hi,x,hivl);
}
long long findMaxAttraction(long long N, long long start, long long days, long long attraction[])
{
long long ans=0;
pair<long long,long long>b[nax];
n=N;st=start;d=days;
for(long long i=1;i<=n;i++)
{
a[i]=attraction[i-1];
b[i].first=-a[i];
b[i].second=i;
dp[i]=-inf;
}
sort(b+1,b+n+1);
for(long long i=1;i<=n;i++)
{
pl[b[i].second]=i;
}
dc1(1,st,st+1,n);
dc2(st,n,1,st-1);
for(long long i=1;i<=n;i++)ans=max(ans,dp[i]);
return ans;
}