Submission #574309

#	Time	Username	Problem	Language	Result	Execution time	Memory
574309		8e7	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	5070 ms	47276 KiB

vault

    //Challenge: Accepted
    #include <bits/stdc++.h>
    #pragma GCC optimize("Ofast")
    using namespace std;
    #ifdef zisk
    void debug(){cout << endl;}
    template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
    template<class T> void pary(T l, T r) {
    	while (l != r) cout << *l << " ", l++;
    	cout << endl;
    }
    #else
    #define debug(...) 0
    #define pary(...) 0
    #endif
    #define ll long long
    #define maxn 12000005
    #define pii pair<int, int>
    #define ff first
    #define ss second
    #define io ios_base::sync_with_stdio(0);cin.tie(0);
    const int inf = 1<<30;
    int dp[maxn];
    int main() {
    	io
    		int m;
    	ll L;
    	cin >> m >> L;
    	vector<ll> a(2*m+1), ex(2*m+1);	
    	ll mins = 0, ans = 0;
    	for (int i = 0;i < 2*m+1;i++) {
    		cin >> a[i];
    		if (i == m) ans += a[i], a[i] = 0;
    	}
    	for (int i = m+1;i < 2*m+1;i++) {
    		ll p = min(a[i], L / (i-m));
    		ans += p;
    		L -= p * (i-m);
    		a[i] -= p;
     
    		ex[i] = min(a[i], (ll)m);
    		ex[2 * m - i] = min(p,(ll)m);
    	}
    	for (int i = 0;i < 2 * m+1;i++) {
    		if (i < m) mins += ex[i] * (i - m);
    	}
    	for (int i = 0;i < maxn;i++) dp[i] = -inf;	
     
    	dp[-mins] = 0;
    	for (int i = 0;i < 2*m+1;i++) {
    		ll cnt = 1;
    		vector<int> num;
    		while (ex[i] >= cnt) {
    			num.push_back(cnt);
    			ex[i] -= cnt;
    			cnt <<= 1;
    		}
    		if (ex[i] > 0) num.push_back(ex[i]);
    		for (int p:num) {
    			if (i - m > 0) {
    				for (int j = maxn - 1;j >= 0;j--) {
    					int val = j + p * (i-m);
    					if (val >= maxn) continue;
    					int del = i < m ? -p : p;
    					dp[val] = max(dp[val], dp[j] + del);
    				}
    			} else {
    				for (int j = 0;j < maxn;j++) {
    					int val = j + p * (i-m);
    					if (val < 0) continue;
    					int del = i < m ? -p : p;
    					dp[val] = max(dp[val], dp[j] + del);
    				}
    			}
    		}
    	}
    	if (L - mins >= maxn || L - mins < 0 || dp[L - mins] < -maxn) cout << "impossible\n";
    	else cout << dp[L - mins]+ans << "\n";
    }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 10 / 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