제출 #612275

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

vault

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll M = 300;
ll a[2*M+1];

ll m, l;

bool dp_vis[M*2+1][2*100*M+1];
ll dp_res[M*2+1][2*100*M+1];

// returns max items that can be picked
ll dp(ll v, ll sum)
{
    if(sum<0) return -1;
    if(v==m+1&&sum==0) return 0;
    if(v==m+1) return -1;
    if(dp_vis[v+m][sum])
        return dp_res[v+m][sum];
    dp_vis[v+m][sum] = 1;

    //cout<<v<<" "<<sum<<"\n";
    ll res = -1;
    for(ll i=0;i<=a[v+m];i++)
    {
        ll r = dp(v+1,sum-(v*i));
        if(r==-1) continue;
        res = max(res, r+i);
    }
    dp_res[v+m][sum] = res;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin>>m>>l;
    for(ll i=-m;i<=m;i++)
        cin>>a[i+m];
    ll r = -1;
    if(l<=M*100)
        r = dp(-m,l);
    if(r==-1) cout<<"impossible\n";
    else cout<<r<<"\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