제출 #1346437

#제출 시각아이디문제언어결과실행 시간메모리
1346437Jakub_WozniakUplifting Excursion (BOI22_vault)C++20
0 / 100
22 ms5548 KiB
#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+maxn)/2+123;
const int zer = maxAsumval/2;
ll A[maxn*2];
ll L;
int dp[maxAsumval];
int dp2[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;
        dp2[i] = -maxn*maxAsumval;
    }
    dp[0] = 0;
    dp2[0] = 0;

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


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


    if(L == 0)
    {
        cout << dp[L] << '\n';
        exit(0);
    }
    if(abs(L) >= maxAsumval)
    {
        cout << "impossible\n";
        exit(0);
    }

    dp[0] = dp2[0];

    int maxi = -maxAsumval;
    for(int i = 0 ; i < maxAsumval ; i++)
    {
        if(i+L >= maxAsumval)continue;
        maxi = max(maxi , dp[i] + dp2[i+L]);
    }

    if(maxi < 0)cout << "impossible\n";
    else cout << maxi << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...