제출 #1322579

#제출 시각아이디문제언어결과실행 시간메모리
1322579simona1230Uplifting Excursion (BOI22_vault)C++20
5 / 100
5094 ms31708 KiB
#include<bits/stdc++.h>
using namespace std;
long long m,l;
long long a[128],b[128];
long long cnt0;
long long s1,s2,s;
void read()
{
    cin>>m>>l;
    for(long long i=m;i>=1;i--)
    {
        cin>>b[i];
        s1+=b[i]*i;
    }
    cin>>cnt0;
    for(long long i=1;i<=m;i++)
    {
        cin>>a[i];
        s2+=a[i]*i;
    }
    s=max(s1,s2);
}

long long dpx[1000001][2];
long long dpy[1000001][2];
void solve()
{
    for(long long i=1;i<=s;i++)
        dpx[i][0]=dpy[i][0]=-1;
    for(long long i=1;i<=m;i++)
    {
        //cout<<"!! "<<i<<'\n';
        long long cr=i%2;
        long long od=1^(i%2);

        for(long long j=0;j<=s;j++)
        {
            dpx[j][cr]=dpx[j][od];
            for(long long c=a[i];c>=0;c--)
            {
                if(j>=c*i&&dpx[j-c*i][od]!=-1)
                {
                    if(dpx[j][cr]==-1)dpx[j][cr]=dpx[j-c*i][od]+c;
                    dpx[j][cr]=max(dpx[j][cr],dpx[j-c*i][od]+c);
                }
            }

            dpy[j][cr]=dpy[j][od];
            for(long long c=b[i];c>=0;c--)
            {
                if(j>=c*i&&dpy[j-c*i][od]!=-1)
                {
                    if(dpy[j][cr]==-1)dpy[j][cr]=dpy[j-c*i][od]+c;
                    dpy[j][cr]=max(dpy[j][cr],dpy[j-c*i][od]+c);
                }
            }

            //cout<<j<<" - "<<dpx[j][cr]<<" "<<dpy[j][cr]<<'\n';
        }
    }

    long long ans=-1;
    //cout<<"! "<<s<<'\n';
    if(abs(l)>s)
    {
        cout<<"impossible"<<'\n';
        return;
    }

    for(long long x=0;x<=s2;x++)
    {
        long long y=l-x;
        if(y>0||abs(y)>s1)continue;
        y=-y;
        long long h=m%2;

        if(dpx[x][h]!=-1&&dpy[y][h]!=-1)
            ans=max(ans,dpx[x][h]+dpy[y][h]);
        //cout<<x<<" "<<dpx[x][h]<<" "<<dpy[x][h]<<'\n';
    }

    if(ans==-1)cout<<"impossible"<<'\n';
    else cout<<ans+cnt0<<'\n';
}

int main()
{
    read();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...