Submission #736234

#	Time	Username	Problem	Language	Result	Execution time	Memory
736234		ksu2009en	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	1 ms	212 KiB

vault

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define endl '\n'

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll m, l;
    cin >> m >> l;
    
    vector<ll>a(2 * m + 1);
    for(auto &i: a)
        cin >> i;
    
    ll s1 = 0, s2 = 0;
    for(int i = -m; i <= 0; i++)
        s1 += i * a[i + m];
    
    for(int i = 0; i <= m; i++)
        s2 += i * a[i + m];
    
    if(l < s1 || l > s2){
        cout << "impossible" << endl;
        return 0;
    }
    
    ll add = abs(s1) + 1;
    
    vector<ll>dp(add + s2 + 10, -1e9), dp2(add + s2 + 10, -1e9);
    dp[0 + add] = 0;
    
    for(int i = 0; i < 2 * m + 1; i++){
        ll num = 0;
        if(i < m)
            num = -(m - i);
        else
            num = i - m;
        
        for(auto &j : dp2)
            j = -1e9;
        dp2[0 + add] = 0;
        
        for(int j = 0; j <= a[i]; j++){
            ll sum = num * j;
            
            for(int num2 = s1; num2 <= s2; num2++){
                if(dp[num2 + add - sum] == (ll)(-1e9))
                    continue;
                
                dp2[num2 + add] = max(dp2[num2 + add], j + dp[num2 + add - sum]);
            }
        }
        
        dp = dp2;
    }
    
    if(dp[l + add] == (ll)(-1e9))
        cout << "impossible" << endl;
    else
        cout << dp[l + add] << endl;
     
    return 0;
}
/*
 1 5
 6 0 6
 
 */

• 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