oj.uz

Submission #576819

# Submission time Handle Problem Language Result Execution time Memory
576819 2022-06-13T14:53:49 Z Lucpp Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1870 ms 8228 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAX = 50*100*101;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll M, L;
    cin >> M >> L;
    vector<ll> a(2*M+1);
    for(int i = 0; i < 2*M+1; ++i) cin >> a[i];
    vector<ll> dp(2*MAX+1, -INF);
    if(L < -MAX){
        cout << "impossible\n";
        return 0;
    }
    dp[MAX] = 0;
    for(int i = 0; i < 2*M+1; ++i){
        if(i == M){
            for(int j = 0; j < 2*MAX+1; ++j) dp[j] += a[M];
            continue;
        }
        int v = (int)(i-M);
        int start = 0;
        if(v < 0) start = (int)(2*MAX+1+v);
        for(int j = start; j < start + abs(v); ++j){
            deque<pair<ll, int>> q;
            for(int k = 0; j+v*k >= 0 && j+v*k < 2*MAX+1; ++k){
                ll x = dp[j+v*k]-k;
                while(!q.empty() && x > q.back().first) q.pop_back();
                q.emplace_back(x, k);
                if(k - q.front().second > min(a[i], M)) q.pop_front();
                dp[j+v*k] = q.front().first + k;
            }
        }
    }
    if(L < 0){
        if(dp[L+MAX] < 0) cout << "impossible\n";
        else cout << dp[L+MAX] << "\n";
        return 0;
    }
    ll ans = -INF;
    if(L <= MAX) ans = dp[MAX+L];
    ll sum = 0;
    ll taken = 0;
    for(int i = 1; i <= M; ++i){
        if(a[M+i] <= M) continue;
        ll take = max(0ll, min(a[M+i]-M, (L-MAX-sum) / i));
        for(; sum+take*i <= L && take <= a[M+i]-M; take++){
            ll nsum = sum+take*i;
            if(L-nsum <= MAX) ans = max(ans, taken+take+dp[MAX+L-nsum]);
        }
        sum += take*i;
        taken += taken;
    }
    if(ans < 0) cout << "impossible\n";
    else cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8148 KB Output is correct
2 Correct 42 ms 8148 KB Output is correct
3 Correct 17 ms 8148 KB Output is correct
4 Correct 148 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 866 ms 8148 KB Output is correct
7 Correct 904 ms 8148 KB Output is correct
8 Correct 865 ms 8212 KB Output is correct
9 Correct 890 ms 8148 KB Output is correct
10 Correct 867 ms 8212 KB Output is correct
11 Correct 830 ms 8228 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8148 KB Output is correct
2 Correct 42 ms 8148 KB Output is correct
3 Correct 17 ms 8148 KB Output is correct
4 Correct 148 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 866 ms 8148 KB Output is correct
7 Correct 904 ms 8148 KB Output is correct
8 Correct 865 ms 8212 KB Output is correct
9 Correct 890 ms 8148 KB Output is correct
10 Correct 867 ms 8212 KB Output is correct
11 Correct 830 ms 8228 KB Output is correct
12 Correct 32 ms 8148 KB Output is correct
13 Correct 52 ms 8148 KB Output is correct
14 Correct 22 ms 8124 KB Output is correct
15 Correct 147 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 821 ms 8148 KB Output is correct
18 Correct 858 ms 8148 KB Output is correct
19 Correct 826 ms 8148 KB Output is correct
20 Correct 905 ms 8148 KB Output is correct
21 Correct 883 ms 8220 KB Output is correct
22 Correct 867 ms 8220 KB Output is correct
23 Correct 1811 ms 8148 KB Output is correct
24 Correct 1797 ms 8148 KB Output is correct
25 Correct 1870 ms 8148 KB Output is correct
26 Correct 1709 ms 8148 KB Output is correct
27 Correct 1708 ms 8148 KB Output is correct
28 Correct 1619 ms 8148 KB Output is correct
29 Correct 1679 ms 8148 KB Output is correct

Subtask #3-1
0 / 10.0

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

Subtask #3-2
0 / 10.0

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

Subtask #4-1
0 / 10.0

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

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8148 KB Output is correct
2 Correct 42 ms 8148 KB Output is correct
3 Correct 17 ms 8148 KB Output is correct
4 Correct 148 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 866 ms 8148 KB Output is correct
7 Correct 904 ms 8148 KB Output is correct
8 Correct 865 ms 8212 KB Output is correct
9 Correct 890 ms 8148 KB Output is correct
10 Correct 867 ms 8212 KB Output is correct
11 Correct 830 ms 8228 KB Output is correct
12 Correct 148 ms 8148 KB Output is correct
13 Incorrect 497 ms 8136 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

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

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8148 KB Output is correct
2 Correct 42 ms 8148 KB Output is correct
3 Correct 17 ms 8148 KB Output is correct
4 Correct 148 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 866 ms 8148 KB Output is correct
7 Correct 904 ms 8148 KB Output is correct
8 Correct 865 ms 8212 KB Output is correct
9 Correct 890 ms 8148 KB Output is correct
10 Correct 867 ms 8212 KB Output is correct
11 Correct 830 ms 8228 KB Output is correct
12 Correct 32 ms 8148 KB Output is correct
13 Correct 52 ms 8148 KB Output is correct
14 Correct 22 ms 8124 KB Output is correct
15 Correct 147 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 821 ms 8148 KB Output is correct
18 Correct 858 ms 8148 KB Output is correct
19 Correct 826 ms 8148 KB Output is correct
20 Correct 905 ms 8148 KB Output is correct
21 Correct 883 ms 8220 KB Output is correct
22 Correct 867 ms 8220 KB Output is correct
23 Correct 1811 ms 8148 KB Output is correct
24 Correct 1797 ms 8148 KB Output is correct
25 Correct 1870 ms 8148 KB Output is correct
26 Correct 1709 ms 8148 KB Output is correct
27 Correct 1708 ms 8148 KB Output is correct
28 Correct 1619 ms 8148 KB Output is correct
29 Correct 1679 ms 8148 KB Output is correct
30 Correct 148 ms 8148 KB Output is correct
31 Incorrect 497 ms 8136 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

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

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8148 KB Output is correct
2 Correct 42 ms 8148 KB Output is correct
3 Correct 17 ms 8148 KB Output is correct
4 Correct 148 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 866 ms 8148 KB Output is correct
7 Correct 904 ms 8148 KB Output is correct
8 Correct 865 ms 8212 KB Output is correct
9 Correct 890 ms 8148 KB Output is correct
10 Correct 867 ms 8212 KB Output is correct
11 Correct 830 ms 8228 KB Output is correct
12 Correct 32 ms 8148 KB Output is correct
13 Correct 52 ms 8148 KB Output is correct
14 Correct 22 ms 8124 KB Output is correct
15 Correct 147 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 821 ms 8148 KB Output is correct
18 Correct 858 ms 8148 KB Output is correct
19 Correct 826 ms 8148 KB Output is correct
20 Correct 905 ms 8148 KB Output is correct
21 Correct 883 ms 8220 KB Output is correct
22 Correct 867 ms 8220 KB Output is correct
23 Correct 1811 ms 8148 KB Output is correct
24 Correct 1797 ms 8148 KB Output is correct
25 Correct 1870 ms 8148 KB Output is correct
26 Correct 1709 ms 8148 KB Output is correct
27 Correct 1708 ms 8148 KB Output is correct
28 Correct 1619 ms 8148 KB Output is correct
29 Correct 1679 ms 8148 KB Output is correct
30 Correct 148 ms 8148 KB Output is correct
31 Incorrect 497 ms 8136 KB Output isn't correct
32 Halted 0 ms 0 KB -