제출 #1011472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011472		User0069	휴가 (IOI14_holiday)	C++17	0 / 100	40 ms	65536 KiB

holiday

#include<bits/stdc++.h>
#include<holiday.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,k,x,y,a[maxn],cur,S,opt[maxn];
long long dp[maxn][3][2];
vector<int> v;
struct node
{
    vector<int> a;
    vector<long long> pfs;
    int l,r;
}ST[maxn*30];
void cons(int id,vector<int> v,int lval,int rval)
{
    if(v.size()==0) return;
    int mid=(lval+rval)/2;
    vector<int> s[2];
    ST[id].a.push_back(0);
    ST[id].pfs.push_back(0);
    for(int i:v)
    {
        int cc=ST[id].a.back()+(a[i]>mid);
        ST[id].a.push_back(cc);
        s[a[i]>mid].push_back(i);
        cc=ST[id].pfs.back()+(a[i]>mid)*a[i];
        ST[id].pfs.push_back(cc);
    }
    v.resize(0);
    if(rval==lval) return;
    if(s[0].size()) cons(ST[id].l=++cur,s[0],lval,mid);
    if(s[1].size()) cons(ST[id].r=++cur,s[1],mid+1,rval);
}
int get(int id,int k,int l,int r,int lval,int rval)
{
    if(id==0||ST[id].a.size()<=1||k<=0) return 0;
    if(lval==rval)
    {
        return min(k,(int)ST[id].a.size())*lval;
    }
    int mid=(lval+rval)/2;
    int s1=ST[id].a[l-1];
    int s2=ST[id].a[r];
    if(s2-s1>k)
    {
        return get(ST[id].r,k,s1+1,s2,mid+1,rval);
    }
    else
    {
        int cnt=ST[id].pfs[r]-ST[id].pfs[l-1];
        return cnt+get(ST[id].l,k-(s2-s1),l-s1,r-s2,lval,mid);
    }
}
void dnc(int l,int r,int optl,int optr,int rev,int jump)
{
    if(l>r) return;
    int mid=(l+r)/2;
    opt[mid]=optl,dp[mid][jump][rev]=0;
    for(int i=optl;i<=optr;i++)
    {
        if(!rev)
        {
            int dd=i-S;
            int cc=get(1,mid-dd*jump,S+1,i,1,1e9);
            if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
        }
        if(rev)
        {
            int dd=S-i;
            int cc=get(1,mid-dd*jump,i,S-1,1,1e9);
            if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
        }
 
    }
    if(l==r) return;
    if(!rev)
    {
        dnc(l,mid-1,optl,opt[mid],rev,jump);
        dnc(mid+1,r,opt[mid],optr,rev,jump);
    }
    if(rev)
    {
        dnc(l,mid-1,opt[mid],optr,rev,jump);
        dnc(mid+1,r,optl,opt[mid],rev,jump);
    }
}
long long findMaxAttraction(int32_t n,int32_t start,int32_t d,int32_t b[])
{
    for(int i=1;i<=n;i++) v.push_back(i);
    for(int i=0;i<n;i++) a[i+1]=b[i];
    cons(1,v,1,1e9);
    S=start;
    dnc(1,d,1,S-1,1,1);
    dnc(1,d,1,S-1,1,2);
    dnc(1,d,S+1,n,0,1);
    dnc(1,d,S+1,n,0,2);
    long long ans=0;
    for(int i=0;i<=d;i++)
    {
        ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
        ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
        if(i<d)
        {
            ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
            ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
        }
    }
    return ans;
}

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