Submission #612361

#	Time	Username	Problem	Language	Result	Execution time	Memory
612361		KrisjanisP	Uplifting Excursion (BOI22_vault)	C++14	5 / 100	5120 ms	464124 KiB

vault

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;

const ll M = 100, A = 100;

ll m, l;
ll a[2*M+1];

bool dp_right_vis[M+1][M*M*A+1];
ll dp_right_res[M+1][M*M*A+1];

// i = [1;m]
ll dp_right(ll i, ll sum)
{
    if(sum<0) return -1;
    if(sum==0) return 0;
    if(i==m+1) return -1;
    if(dp_right_vis[i][sum])
        return dp_right_res[i][sum];
    ll res = -1;
    for(ll j=min(sum/i,a[m+i]);j>=0;j--)
    {
        ll r = dp_right(i+1,sum-i*j);
        if(r==-1) continue;
        res = max(res,r+j);
        break;
    }
    dp_right_vis[i][sum] = 1;
    dp_right_res[i][sum] = res;
    return res;
}

bool dp_left_vis[M+1][M*M*A+1];
ll dp_left_res[M+1][M*M*A+1];

// i = [1;m]
ll dp_left(ll i, ll sum)
{
    if(sum<0) return -1;
    if(sum==0) return 0;
    if(i==m+1) return -1;
    if(dp_left_vis[i][sum])
        return dp_left_res[i][sum];
    ll res = -1;
    for(ll j=min(sum/i,a[m-i]);j>=0;j--)
    {
        ll r = dp_left(i+1,sum-i*j);
        if(r==-1) continue;
        res = max(res,r+j);
        break;
    }
    dp_left_vis[i][sum] = 1;
    dp_left_res[i][sum] = res;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    cin>>m>>l;
    for(ll i=0;i<2*m+1;i++)
        cin>>a[i];
    ll res = a[0];
    bool found = false;
    ll mn=0,mx=0;
    for(ll i=-m;i<0;i++)
        mn+=a[i+m]*i;
    for(ll i=1;i<=m;i++)
        mx+=a[i+m]*i;
    //cout<<mn<<" "<<mx<<"\n";
    for(ll x=0;x<=-mn;x++)
    {
        ll y = l+x;
        if(y>mx) break;
        ll left_res = dp_left(1,x);
        if(left_res==-1) continue;
        ll right_res = dp_right(1,y);
        if(right_res==-1) continue;
        found = true;
        //cout<<"x y: "<<x<<" "<<y<<endl;
        //cout<<left_res<<" "<<right_res<<endl;
        res = max(res,left_res+right_res+a[m]);
    }
    if(found)
        cout<<res<<"\n";
    else
        cout<<"impossible\n";
}

• 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