Submission #969411

#	Time	Username	Problem	Language	Result	Execution time	Memory
969411		vjudge1	휴가 (IOI14_holiday)	C++17	0 / 100	22 ms	65536 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
#define II signed
#define int long long
using namespace std;
int optL[3000],optR[3000],valL[7500],valR[7500],sums[3000][3000];
void MLE(){
    vector<int>v;
    for(;;)
        v.push_back(12);
}
int proc(II n, II &start, II d,II arr[]){
    memset(sums,0,sizeof sums);
    memset(valL,0,sizeof valL);
    memset(valR,0,sizeof valR);
    multiset<int> st;
    for(int i=start;i>-1;i--){
        st.insert(arr[i]);
        auto it=st.end();
        for(int j=1;j<=start-i+1;j++)
            it--,sums[i][j]=sums[i][j-1]+*it;
        for(int j=start-i+2;j<=d;j++)
            sums[i][j]=sums[i][j-1];
    }
    st.clear();
    for(int i=start;++i<n;){
        st.insert(arr[i]);
        auto it=st.end();
        for(int j=1;j<=i-start;j++)
            it--,sums[i][j]=sums[i][j-1]+*it;
        for(int j=i-start+1;j<=d;j++)
            sums[i][j]=sums[i][j-1];
    }
    for(int i=0;++i<=d;)
        for(int j=0;j<=start;j++)
            if(2*(start-j)<i&&valL[i]<sums[j][min((long long)n,i-2*(start-j))])
                valL[i]=sums[j][i-2*(start-j)],optL[i]=j;
    for(int i=2;i<=d;i++)
        if(optL[i]>optL[i-1])
            MLE();
    for(int i=0;++i<=d;)
        for(int j=start;j<=n;j++)
            if(j-start<i&&valR[i]<!!(j-start)*sums[j][min((long long)n,i-j+start)])
                valR[i]=sums[j][i-j+start],optR[i]=j;
    for(int i=2;i<=d;i++)
        if(optR[i]<optR[i-1])
            MLE();
    int ANS=0;
    for(int i=0;i<=d;i++)
        ANS=max(ANS,valL[i]+valR[d-i]);
    reverse(arr,arr+n);
    start=n-1-start;
    return ANS;
}
int findMaxAttraction(II n, II start, II d, II attraction[]) {
    return max(proc(n,start,d,attraction),proc(n,start,d,attraction));
}

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