제출 #987215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987215		alexdd	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	2 ms	860 KiB

vault

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAXV = 300;
int m,L;
int a[700];
int dp[700][2*MAXV+5];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>m>>L;
    for(int i=-MAXV;i<=MAXV;i++)
        dp[0][MAXV+i]=-INF;
    dp[0][MAXV+0]=0;
    for(int i=-m;i<=m;i++)
    {
        cin>>a[m+i+1];
        for(int sum=-MAXV;sum<=MAXV;sum++)
        {
            dp[m+i+1][MAXV+sum] = dp[m+i][MAXV+sum];
            for(int cnt=1;cnt<=a[m+i+1];cnt++)
            {
                if(abs(sum - cnt*i) > MAXV)
                    break;
                if(dp[m+i][MAXV+sum-cnt*i] > -INF) dp[m+i+1][MAXV+sum] = max(dp[m+i+1][MAXV+sum], dp[m+i][MAXV+sum-cnt*i] + cnt);
            }
        }
    }
    int rez=-INF;
    if(abs(L)<=abs(MAXV))
    {
        rez = dp[2*m+1][MAXV+L];
    }
    else
    {
        for(int d=1;d<=m;d++)
        {
            int r = L%d;
            for(int cnt=0;r+cnt*d<=MAXV;cnt++)
            {
                rez = max(rez, dp[2*m+1][MAXV+r+cnt*d] + L/d - cnt);
            }
        }
    }
    if(rez==-INF)
        cout<<"impossible";
    else
        cout<<rez;
    return 0;
}

• 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