oj.uz

Submission #653532

# Submission time Handle Problem Language Result Execution time Memory
653532 2022-10-27T08:32:06 Z erto Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1141 ms 1856 KB 
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF (int)(1e9 + 7)
#define INF2 998244353
#define N (ll)(3e2 + 5)
//#define f first
//#define s second
#define int ll
#define lsb(x) (x & (-x))
using namespace std;

int n, m, g, h, l;

int a[1000];
int dp1[100000], dp2[100000];
int cnt1[100000], cnt2[100000];
int sum = 0;

int f1(int x){
    int sum = 0;
    while(x){
        sum += cnt1[x];
        x -= cnt1[x] * dp1[x];
    }
    return sum;
}

int f2(int x){
    int sum = 0;
    while(x){
        sum += cnt2[x];
        x -= cnt2[x] * dp2[x];
    }
    return sum;
}

void solve(){
    cin >> m >> l;
    for(int i=0; i<2*m+1; i++){
        cin >> a[i];
        if(i > m){
            sum += (i - m) * a[i];
        }
    }

    int ans = a[m];
    int cur = 0;
    int t1, t2;

    dp1[0] = dp2[0] = 1;

    if(sum < l){
        cout << "impossible";
        return;
    }
    bool bb = 0;

    for(int i=m+1; i<=2*m; i++){
        g = (l - cur) / (i - m);
        h = min(g, a[i]);
        ans += h;
        cur += h * (i - m);
        t1 = h;
        t2 = a[i] - h;

        if(cur == l){
            bb=1;
            break;
        }

        for(int k=99000; k; k--){
            if(dp1[k])continue;
            for(int j=1; j<=t1 && j * (i - m) <= k; j++){
                if(dp1[k - j * (i - m)]){
                    dp1[k] = (i - m);
                    cnt1[k] = j;
                }
            }
        }

        for(int k=99000; k; k--){
            if(dp2[k])continue;
            for(int j=1; j<=t2 && j * (i - m) <= k; j++){
                if(dp2[k - j * (i - m)]){
                    dp2[k] = (i - m);
                    cnt2[k] = j;
                }
            }
        }

        int dif = l - cur;
        for(int j=dif; j<=min(l, 99000ll); j++){
            if(dp2[j] > 0 && dp1[j - dif] > 0){
                bb = 1;
                ans -= f1(j - dif);
                ans += f2(j);
            }
        }
        if(bb)break;
    }

    if(!bb){
        cout << "impossible";
        return;
    }

    cout << ans;
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    for(int i=1; i<=T; i++){
        solve();
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1141 ms 1856 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 0 ms 340 KB Output is correct
2 Incorrect 1141 ms 1856 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 0 ms 340 KB Output is correct
2 Incorrect 1141 ms 1856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

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

Subtask #5-1
0 / 10.0

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

Subtask #5-2
0 / 10.0

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

Subtask #6-1
0 / 10.0

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

Subtask #6-2
0 / 10.0

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