oj.uz

Submission #937142

# Submission time Handle Problem Language Result Execution time Memory
937142 2024-03-03T14:19:41 Z berr Uplifting Excursion (BOI22_vault) C++17
50 / 100
 5 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
       int n, m; cin >> n >> m;
    vector<int> a(n*2+1);
    int sum=0, el = 0, top=0;
 
    for(int i=-1*n; i<=n; i++){
        cin >> a[i+n];
        sum+=i*a[i+n]; el+=a[i+n];
    }
 
    m = sum-m;
    vector<int> used(n*2+1);
    int hedef;
 
    if(m<0){
        int sum=0;
        for(int i=-n; i<0; i++){
            if(a[i+n]==0) continue;
            if(sum+a[i+n]*i > m){
                used[i+n]=a[i+n];
                sum+=a[i+n]*i;
                top+=a[i+n];
                a[i+n]=0;
            }
            else if(sum > m){
                int s=0;
                for(int l=50; l>=0; l--){
                    int tmp = s+(1LL<<l);
                    if(tmp > a[i+n]) continue;
                    if(tmp*i+sum > m){
                        s=tmp;
                    }
                }
                s++;
                sum+=s*i;
                top+=s;
                used[i+n] =s;
                a[i+n]-=s;
            }
        }
 
        if(sum>m){
            cout<<"impossible";
            return 0;
        }
        else hedef = m-sum;
    }
    else{
        int sum=0;
        for(int i=n; i>0; i--){
            if(a[i+n]==0) continue;
            if(sum+a[i+n]*i < m){
                used[i+n]=a[i+n];
                sum+=a[i+n]*i;
                top+=a[i+n];
                a[i+n]=0;
            }
            else if(sum < m){
                int s=0;
                for(int l=50; l>=0; l--){
                    int tmp = s+(1LL<<l);
                    if(tmp > a[i+n]) continue;
                    if(tmp*i+sum < m){
                        s=tmp;
                    }
                }
                s++;
                top+=s;
                sum+=s*i;
                used[i+n] =s;
                a[i+n]-=s;
            }
        }
 
        if(sum<m){
            cout<<"impossible";
            return 0;
        }
        else hedef = m-sum;
    }
 

    vector<int>  val(4*n+1, 1e18);

    val[2*n]=0;

    int mi=0, h=0;
    int pf=1;


    while(pf){
        h++;
        int flag = 0;
        vector<int> pre;
        pre = val;
 
        for(int i=-n; i<=n; i++){
            if(used[i+n]>0){
                int check =0;
                for(int l=-2*n; l<=2*n; l++){
                    if(l-i>=-2*n&&l-i<=2*n)
                    if(pre[l+2*n]<=mi && val[(l-i)+2*n] > pre[l+2*n]-1){
                        check = 1;
                        val[(l-i+2*n)]=pre[l+2*n]-1;
                    }
                }
 
                if(check){
                    flag = 1;
                    used[i+n]--;
                }
            }
        }
//        if(flag) mi--;

        if(!flag){
            int check = 0;
            for(int i=-n; i<=n; i++){
                int check2=0;
                if(a[i+n]>0){
                    for(int l=-2*n; l<=2*n; l++){
                        if(l+i>=-2*n && l+i<=2*n){
                            if(val[l+2*n]<=mi && val[(l+i)+2*n]>val[l+2*n]+1){
                                check2 = 1;
                                val[(l+i)+2*n] = val[l+2*n]+1;
                            }
                        }
                    }
 
                    if(check2) a[i+n]--, check=1;
                }
            }

            for(int l=-2*n; l<=2*n; l++){
                if(val[l+2*n]==mi) check=1;
            }
            if(check) mi++;
            else pf=0;
        }
        
    }


    if(val[hedef+2*n]!=1e18){
        cout<<el-(top+val[hedef+2*n]);
    }   
    else cout<<"impossible";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3-2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 392 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 452 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct

Subtask #4-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 600 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 460 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 5 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 600 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 460 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 5 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 1 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 1 ms 348 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 1 ms 600 KB Output is correct
65 Correct 1 ms 348 KB Output is correct
66 Correct 0 ms 600 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 1 ms 348 KB Output is correct
69 Correct 1 ms 348 KB Output is correct
70 Correct 0 ms 456 KB Output is correct
71 Correct 1 ms 348 KB Output is correct
72 Correct 1 ms 348 KB Output is correct
73 Correct 1 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 1 ms 348 KB Output is correct
76 Correct 1 ms 348 KB Output is correct
77 Correct 1 ms 348 KB Output is correct
78 Correct 1 ms 344 KB Output is correct
79 Correct 5 ms 348 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 3 ms 452 KB Output is correct
82 Correct 1 ms 344 KB Output is correct
83 Correct 3 ms 348 KB Output is correct
84 Correct 4 ms 348 KB Output is correct
85 Correct 2 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 2 ms 348 KB Output is correct

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -