제출 #720152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720152		Rafi22	Uplifting Excursion (BOI22_vault)	C++14	5 / 100	1431 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];

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=-4*m*m;i<=4*m*m;i++) DP[i+4*m*m]=-infl;
    DP[4*m*m]=0;
    for(int i=-m;i<=m;i++)
    {
        for(int j=-4*m*m;j<=4*m*m;j++)
        {
            for(int l=1;l<=min((ll)2*m+1,a[i+m]+b[i+m]);l++)
            {
                int k=j+l*i;
                if(k<-4*m*m||k>4*m*m) continue;
                ll x=min(a[i+m],(ll)l)-max(0LL,l-a[i+m]);
                DP[k+4*m*m]=max(DP[k+4*m*m],DP[j+4*m*m]+x);
            }
        }
    }
    l-=act;
    if(l<-4*m*m||l>4*m*m) gg();
    else
    {
        if(ans+DP[l+4*m*m]<0) gg();
        cout<<ans+(ll)DP[l+4*m*m];
    }

    return 0;
}

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