Submission #1310722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310722		cansu_mutlu	Uplifting Excursion (BOI22_vault)	C++20	0 / 100	1 ms	568 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];
        //cout << i <<"  "<< a[i] << endl;
        
    }
    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)
        {
            //cout << i << " "<< a[i] <<"  "<< var[i] << endl;
            cur+=num;
            cnt+=a[i];
            var[i] = a[i];
            a[i] = 0;
            //cout << i << " "<< a[i] <<"  "<< var[i] << endl;
        }
        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<< " "<< var[i] <<" "<< a[i] << endl;
        for(int num = 1;num<=min(m,var[i]);num++)
        {
          //  cout << num << endl;
            for(int cur = 2*m*m-i;cur>=0;cur--)
            {
                   // cout << i << " " << cur << " "<< dp[cur] << " "<< dp[cur+i] << endl;
                    dp[cur] = max(dp[cur],dp[cur+i]-1);
            }
        }
        for(int num=1;num<=min(m,a[i]);num++)
        {
            for(int cur =i;cur<=m*m*2;cur++)
            {
                if(dp[cur-i]!=0)
                {
                    dp[cur] = max(dp[cur],dp[cur-i]+1);
                }
            }
        }
        
    }
   /* for(int i=1;i<=m;i++)
    {
        //cout << i<< " "<< var[i] <<" "<< a[i] << endl;
       
        for(int num=1;num<=min(m,a[i]);num++)
        {
            for(int cur = 2*m;cur>=i;cur--)
            {
                if(dp[cur-i]!=0)
                {
                    dp[cur] = max(dp[cur],dp[cur-i]+1);
                }
            }
        }
    }*/
   // for(int i=0;i<=2*m;i++) cout <<i << " "<< dp[i] << endl;
   // cout << dp[m*m] << endl;
    if(l!=0 && dp[m*m]==0)
    {
        cout << "impossible" << endl;
    }
    else cout << sifir+dp[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