oj.uz

Submission #736232

# Submission time Handle Problem Language Result Execution time Memory
736232 2023-05-05T10:52:29 Z ksu2009en Uplifting Excursion (BOI22_vault) C++14
0 / 100
 0 ms 212 KB 
#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);
    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(int num2 = s1; num2 <= s2; num2++)
            dp2[num2 + add] = -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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -