제출 #1310723

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

vault

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,l;
    cin >> m>> l;
    vector<int> a(m+1);
    int sifir = 0;
    int sum = 0;
    vector<int> eksi(m+1);
    for(int i=m;i>=1;i--) cin >> eksi[i];
    cin >> sifir;
    for(int i=1;i<=m;i++) 
    {
        cin >> a[i];
        
    }
    int cur = 0,cnt=0;
    vector<int> var(m+1,0);
    for(int i=1;i<=m;i++)
    {
        int num = a[i]*i;
        if(num+cur<=l+m)
        {
            cur+=num;
            cnt+=a[i];
            var[i] = a[i];
            a[i] = 0;
        }
        else
        {
            int istek = l+m-cur;
            istek/=i;
            cur+= i*istek;
            cnt+=istek;
            var[i] = istek;
            a[i]-=istek;
        }
    }
    if(cur<l-m)
    {
        cout << "impossible" << endl;
        return 0;
    }
    cur-=l;
    cur+=m*m;
    //cout << cur << " "<< cnt << endl;
    vector<int> dp(2*m*m+1,0);
    dp[cur] = cnt;
    for(int i=1;i<=m;i++)
    {
        //cout << i << endl;
        for(int num = 1;num<=min(m,var[i]);num++)
        {
            for(int cur = 0;cur<=2*m*m-i;cur++)
            {
                if(dp[cur+i]!=0)
                {
                    dp[cur] = max(dp[cur],dp[cur+i]-1);
                }
            }
        }
        for(int num=1;num<=min(m,a[i]);num++)
        {
            for(int cur = 2*m*m;cur>=i;cur--)
            {
                if(dp[cur-i]!=0)
                {
                    dp[cur] = max(dp[cur],dp[cur-i]+1);
                }
            }
        }
    }
    if(l!=0 && dp[m*m]==0)
    {
        cout << "impossible" << endl;
    }
    else cout << sifir+dp[m*m] << endl;
}

• 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