oj.uz

Submission #595675

# Submission time Handle Problem Language Result Execution time Memory
595675 2022-07-14T00:34:36 Z definitelynotmee Uplifting Excursion (BOI22_vault) C++
0 / 100
 26 ms 4180 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1<<30;
const int MAXVAL = 505050;

struct smartvec{
    vector<int> dp;
    smartvec(){
        dp = vector<int>(2*MAXVAL+1,-INF);
    }
    int& operator[](int id){
        return dp[id+MAXVAL];
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll m, l;
    cin >> m >> l;
    if(abs(l) >= MAXVAL){
        cout << "impossible\n";
        return 0;
    }

    vector<pll> v;

    for(int i = -m; i <= m; i++){
        int in;
        cin >> in;
        for(int bit = 0; in; bit++){
            int ct = min(1<<bit,in);
            v.push_back({i*ct,ct});
            in-=ct;
        }
    }
    cout << v.size() << '\n';
    smartvec dp;
    dp[0] = 0;
    
    for(pii i : v){
        if(i.ff >= 0){
            for(int x = MAXVAL-1; x >= -MAXVAL+i.ff; x--){
                dp[x] = max(dp[x],dp[x-i.ff]+i.ss);
            }
        } else {
            for(int x = -MAXVAL; x < MAXVAL+i.ff; x++){
                dp[x] = max(dp[x],dp[x-i.ff]+i.ss);
            }
        }
        // cout << "iteracao " << i.ff << ' ' << i.ss << "=>" << endl;
        // for(int i = -l; i <= l; i++){
        //     cout << i << ": " << dp[i] << endl;
        // }
    }
    
    if(dp[l] >= 0){
        cout << dp[l] << '\n';
    } else cout << "impossible\n";
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 4180 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 26 ms 4180 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 26 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

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

Subtask #5-1
0 / 10.0

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

Subtask #5-2
0 / 10.0

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

Subtask #6-1
0 / 10.0

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

Subtask #6-2
0 / 10.0

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