Submission #720170

#	Time	Username	Problem	Language	Result	Execution time	Memory
720170		Rafi22	Uplifting Excursion (BOI22_vault)	C++14	80 / 100	1605 ms	972 KiB

vault

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int M=207;

ll a[2*M];
ll b[2*M];

ll DP[M*M*4];
ll nDP[M*M*4];

void gg()
{
    cout<<"impossible";
    exit(0);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    ll l,sum=0,ans=0,act=0;
    cin>>m>>l;
    for(ll i=-m;i<=m;i++)
    {
        cin>>a[i+m];
        sum+=a[i+m]*i;
    }
    ans+=a[m];
    a[m]=0;
    if(sum>=l)
    {
        for(ll i=-m;i<=m;i++)
        {
            ll x;
            if(i<=0) x=a[i+m];
            else x=min(a[i+m],(l-act)/i);
            b[-i+m]+=x;
            a[i+m]-=x;
            ans+=x;
            act+=i*x;
        }
    }
    else
    {
        for(ll i=m;i>=-m;i--)
        {
            ll x;
            if(i>=0) x=a[i+m];
            else x=min(a[i+m],(l-act)/i);
            b[-i+m]+=x;
            a[i+m]-=x;
            ans+=x;
            act+=x*i;
        }
    }
    for(int i=-2*m*m;i<=2*m*m;i++) DP[i+2*m*m]=-infl;
    DP[2*m*m]=0;
    for(int i=-m;i<=m;i++)
    {
        for(int j=-2*m*m;j<=2*m*m;j++) nDP[j+2*m*m]=-infl;
        for(int j=-2*m*m;j<=2*m*m;j++)
        {
            for(int l=0;l<=min((ll)2*m,a[i+m]+b[i+m]);l++)
            {
                int k=j+l*i;
                if(k<-2*m*m||k>2*m*m) continue;
                ll x=min(a[i+m],(ll)l)-max(0LL,l-a[i+m]);
                nDP[k+2*m*m]=max(nDP[k+2*m*m],DP[j+2*m*m]+x);
            }
        }
        for(int j=-2*m*m;j<=2*m*m;j++) DP[j+2*m*m]=nDP[j+2*m*m];
    }
    l-=act;
    if(l<-2*m*m||l>2*m*m) gg();
    else
    {
        if(ans+DP[l+2*m*m]<0) gg();
        cout<<ans+(ll)DP[l+2*m*m];
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10