Submission #1078634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078634		LIF	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	1149 ms	17232 KiB

vault

#include<bits/stdc++.h>
using namespace std;
long long int m,dp[10800005];
long long int L;
int num[200005];
int val[200005];
int num2[500005];
int val2[500005];
int all = 0;
int main()
{
    cin>>m>>L;
    for(int i=1;i<=m*2+1;i++)
    {
        cin>>num[i];
        val[i] = i-m-1;
    }
    for(int i=0;i<=520000*2;i++)dp[i] = -1;
    dp[520000] = 0; //遍移量為520000
    int last = 0;
    for (int i=m+1;i<=m*2+1;i++)
    {
        for(int j=1;j<=num[i];j*=2)
        {
            if(num[i] >= j)
            {
                num[i] -= j;
                all++;
                num2[all] = j;
                val2[all] = j*val[i];
            }
        }
        if(num[i] > 0)
        {
            all++;
            num2[all] = num[i];
            val2[all] = num[i] * val[i];
        }
        for(int j=last+1;j<=all;j++)
        {
            for(int k=520000*2;k>=1;k--)
            {
                if(k >= val2[j])
                {
                    if(dp[k-val2[j]] == -1)continue;
                    if(dp[k] == -1)
                    {
                        dp[k] = dp[k-val2[j]] + num2[j];   
                    }           
                    else dp[k] = max(dp[k-val2[j]] + num2[j],dp[k]);
                }
            }
        }
        last = all;
    }
    for (int i=1;i<=m;i++)
    {
        for(int j=1;j<=num[i];j*=2)
        {
            if(num[i] >= j)
            {
                num[i] -= j;
                all++;
                num2[all] = j;
                val2[all] = j*val[i];
            }
        }
        if(num[i] > 0)
        {
            all++;
            num2[all] = num[i];
            val2[all] = num[i] * val[i];
        }
        for(int j=last+1;j<=all;j++)
        {
            for(int k=1;k<=520000*2;k++)
            {
                if(k -val2[j] <= 520000*2)
                {
                    if(dp[k-val2[j]] == -1)continue;
                    if(dp[k] == -1)
                    {
                        dp[k] = dp[k-val2[j]] + num2[j];   
                    }           
                    else dp[k] = max(dp[k-val2[j]] +num2[j],dp[k]);
                }
            }
        }
        last = all;
    }
    // for(int i=1;i<=all;i++)
    // {
    //     cout<<num2[i]<<" "<<val2[i]<<endl;
    // }
    if(L >= 520000 || L <= 0-520000)
    {
        cout<<"impossible"<<endl;
        return 0;
    }
    else
    {
        if(dp[L+520000] >= 0)cout<<dp[L+520000]<<endl;
        else cout<<"impossible"<<endl;
    }

    








    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 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