Submission #712291

#	Time	Username	Problem	Language	Result	Execution time	Memory
712291		bin9638	Shortcut (IOI16_shortcut)	C++17	71 / 100	1485 ms	175308 KiB

shortcut

#include <bits/stdc++.h>

#ifndef SKY
#include "shortcut.h"
#endif // SKY

using namespace std;

#define ll long long
#define pb push_back
#define N 4010
#define ii pair<ll,int>
#define fs first
#define sc second

int n;
ll sum[N],C,d[N],left_pair[N],right_pair[N],l[N],r[N],f[N][N],dp[N][N];

struct rmq
{
    ll rmq[N][21]={};
    int LOG;

    void init(ll val)
    {
        memset(rmq,-0x3f3f,sizeof(rmq));
        LOG=log2(n);
        for(int i=1;i<=n;i++)
            rmq[i][0]=sum[i]*val+d[i];
        for(int k=1;k<=LOG;k++)
            for(int i=1;i<=n;i++)
                if(i+(1<<(k-1))<=n)
                    rmq[i][k]=max(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
    }

    ll get_max(int l,int r)
    {
        int k=31-__builtin_clz(r-l+1);
        return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
    }
}tru,cong;

bool check(ll x)
{
    memset(dp,-0x3f3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(sum[j]-sum[i]+d[i]+d[j]>x)
            {
               // cout<<i<<" "<<j<<" "<<d[i]+sum[i]+d[j]-sum[j]<<endl;
                dp[i][j]=d[i]+sum[i]+d[j]-sum[j];
            }
    for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++)
        {
            if(i<j)
                dp[i][j]=max(dp[i][j],dp[i+1][j]);
            if(i<j)
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
            if(dp[i][j]-sum[i]+sum[j]+C<=x&&f[i][j]<=x)
            {
              //  cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<-sum[i]+sum[j]<<endl;
                return 1;
            }
        }
    return 0;
}

ll find_shortcut(int cc, vector<int> vc, vector<int> DD, int vl)
{
    n=cc;
    C=vl;
    for(int i=2;i<=n;i++)
        sum[i]=1ll*vc[i-2]+sum[i-1];
    for(int i=1;i<=n;i++)
        d[i]=DD[i-1];
    memset(l,-0x3f3f,sizeof(l));
    memset(r,-0x3f3f,sizeof(r));
    for(int i=1;i<=n;i++)
    {
        l[i]=d[i]-sum[i];
        if(i>1)
            l[i]=max(l[i],l[i-1]);
        left_pair[i]=left_pair[i-1];
        for(int j=1;j<i;j++)
            left_pair[i]=max(left_pair[i],sum[i]-sum[j]+d[i]+d[j]);
       // cout<<l[i]<<" "<<left_pair[i]<<endl;
    }
    for(int i=n;i>=1;i--)
    {
        r[i]=d[i]+sum[i];
        if(i<n)
            r[i]=max(r[i],r[i+1]);
        right_pair[i]=right_pair[i+1];
        for(int j=n;j>i;j--)
            right_pair[i]=max(right_pair[i],sum[j]-sum[i]+d[i]+d[j]);
    }
    tru.init(-1);
    cong.init(1);
    for(int i=1;i<=n;i++)
    {
        int pos=i;
        for(int j=i;j<=n;j++)
        {
            f[i][j]=max(left_pair[i],max(right_pair[j],l[i]+r[j]+sum[i]-sum[j]+min(C,sum[j]-sum[i])));
           // if(i==1&&j==9)cout<<f[i][j]<<endl;
            while(pos<j&&sum[pos+1]-sum[i]<=sum[j]-sum[pos+1]+min(C,sum[j]-sum[i]))
                pos++;
            f[i][j]=max(f[i][j],l[i-1]+cong.get_max(i,pos));
            if(pos<j)
            {
                f[i][j]=max(f[i][j],l[i-1]+sum[i]+sum[j]+tru.get_max(pos+1,j)+min(C,sum[j]-sum[i]));
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        int pos=i;
        for(int j=i;j>=1;j--)
        {
            while(pos>j&&sum[i]-sum[pos-1]<=sum[pos-1]-sum[j]+min(C,sum[i]-sum[j]))
                pos--;
            f[j][i]=max(f[j][i],r[i+1]+tru.get_max(pos,i));
          //  if(j==2&&i==4)
            //    cout<<pos<<" "<<r[i]<<" "<<tru.get_max(pos,i)<<endl;
            if(pos>j)
            {
                f[j][i]=max(f[j][i],r[i+1]-sum[i]+cong.get_max(j,pos-1)-sum[j]+min(C,sum[i]-sum[j]));
            }
        }
    }

    ll u=1,v=1e13,res=0;
    while(u<=v)
    {
        ll mid=(u+v)/2;
        if(check(mid))
        {
            res=mid;
            v=mid-1;
        }else
            u=mid+1;
    }
    return res;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n,c;
    vector<int>l,d;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int u;
        cin>>u;
        l.pb(u);
    }
    for(int i=0;i<n;i++)
    {
        int u;
        cin>>u;
        d.pb(u);
    }
    cin>>c;
    cout<<find_shortcut(n,l,d,c);
}
#endif

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3