Submission #1346412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1346412		Jakub_Wozniak	Uplifting Excursion (BOI22_vault)	C++20	5 / 100	5089 ms	2964 KiB

vault

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define st first
#define nd second
const int maxn = 109;
const int maxAsumval = maxn*(maxn*maxn)/2+123;
const int zer = maxAsumval/2;
ll A[maxn*2];
ll L;
int dp[maxAsumval];


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int M;
    cin >> M >> L;

    for(int i = 0; i < 2*M+1 ; i++)
    {
        cin >> A[i];
    }
    //A[i] ma A[i-M] tak naprawde

    for(int i = 0 ; i < maxAsumval ; i++)
    {
        dp[i] = -maxn*maxAsumval;
        if(i == zer)dp[i] = 0;
    }

    for(int i = 0; i < 2*M+1 ; i++)
    {
        for(int l = 0 ; l < A[i] ; l++)
        {
            if(i < M)// ujemne
            {
                for(int j = 0 ; j < maxAsumval ; j++)
                {
                    if((j-(i-M)) >= maxAsumval)continue;
                    dp[j] = max(dp[j] , dp[j-(i-M)]+1);
                }
            }
            else
            {
                for(int j = maxAsumval-1 ; j >= 0 ; j--)                
                {
                    if((j-(i-M)) < 0)continue;
                    dp[j] = max(dp[j] , dp[j-(i-M)]+1);
                }
            }
        }
        
    }

    if(abs(L+zer) >= maxAsumval || dp[L+zer] < 0)cout << "impossible\n";
    else cout << dp[L+zer] << '\n';

    return 0;
}

• 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