제출 #612316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612316		KrisjanisP	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	5061 ms	277272 KiB

vault

#include <bits/stdc++.h>

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=0;j<=a[m+i];j++)
    {
        ll r = dp_right(i+1,sum-i*j);
        if(r==-1) continue;
        res = max(res,r+j);
    }
    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=0;j<=a[m-i];j++)
    {
        ll r = dp_left(i+1,sum-i*j);
        if(r==-1) continue;
        res = max(res,r+j);
    }
    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;
    for(ll x=0;x<=M*M*A;x++)
    {
        ll y = l+x;
        if(y>M*M*A) continue;
        ll left_res = dp_left(1,x);
        ll right_res = dp_right(1,y);
        if(left_res==-1||right_res==-1) continue;
        found = true;
        res = max(res,left_res+right_res+a[m]);
    }
    if(found)
        cout<<res<<"\n";
    else
        cout<<"impossible\n";
}

• Subtask 1: 0 / 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