oj.uz

Submission #653526

# Submission time Handle Problem Language Result Execution time Memory
653526 2022-10-27T08:23:30 Z erto Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1 ms 340 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)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<=99000; 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 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 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 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 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 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 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -