Submission #573078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
573078	2022-06-05T17:40:05 Z	MohamedFaresNebili	Uplifting Excursion (BOI22_vault)	C++14	5 / 100	970 ms	417248 KB

vault

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
 
        using namespace std;
 
        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
 
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
		#define int ll
 
        const int oo = 1e9 + 7;
 
        int N, M, A[1000];
        int DP[105][250005];
        int solve(int i, int state) {
            if(i == 2 * N + 1) {
                if(state == M) return 0;
                return -oo;
            }
            if(DP[i][state] != -1)
                return DP[i][state];
            int best = -oo;
            for(int l = 0; l <= A[i]; l++) {
              	int calc = solve(i + 1, state + l * (i - N));
              	if(calc != -oo)
               		 best = max(best,
                    	l + solve(i + 1, state + l * (i - N)));
            }
            return DP[i][state] = best;
        }
 
        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> M; memset(DP, -1, sizeof DP);
            for(int l = 0; l <= 2 * N; l++) cin >> A[l];
            int ans = solve(0, 0);
            if(ans == -oo) cout << "impossible\n";
            else cout << ans << "\n";
        }

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	205704 KB	Output is correct
2	Correct	85 ms	205712 KB	Output is correct
3	Correct	95 ms	205696 KB	Output is correct
4	Correct	98 ms	205760 KB	Output is correct
5	Correct	309 ms	205796 KB	Output is correct
6	Correct	542 ms	205792 KB	Output is correct
7	Correct	148 ms	205680 KB	Output is correct
8	Correct	408 ms	205796 KB	Output is correct
9	Correct	970 ms	205800 KB	Output is correct
10	Correct	80 ms	205732 KB	Output is correct
11	Correct	101 ms	205788 KB	Output is correct

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	205704 KB	Output is correct
2	Correct	85 ms	205712 KB	Output is correct
3	Correct	95 ms	205696 KB	Output is correct
4	Correct	98 ms	205760 KB	Output is correct
5	Correct	309 ms	205796 KB	Output is correct
6	Correct	542 ms	205792 KB	Output is correct
7	Correct	148 ms	205680 KB	Output is correct
8	Correct	408 ms	205796 KB	Output is correct
9	Correct	970 ms	205800 KB	Output is correct
10	Correct	80 ms	205732 KB	Output is correct
11	Correct	101 ms	205788 KB	Output is correct
12	Correct	101 ms	205732 KB	Output is correct
13	Correct	82 ms	205764 KB	Output is correct
14	Correct	81 ms	205748 KB	Output is correct
15	Correct	77 ms	205728 KB	Output is correct
16	Correct	261 ms	205800 KB	Output is correct
17	Correct	467 ms	205800 KB	Output is correct
18	Correct	120 ms	205708 KB	Output is correct
19	Correct	350 ms	205716 KB	Output is correct
20	Correct	778 ms	205696 KB	Output is correct
21	Correct	77 ms	205792 KB	Output is correct
22	Correct	78 ms	205716 KB	Output is correct
23	Runtime error	262 ms	417188 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	205700 KB	Output is correct
2	Runtime error	498 ms	417248 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	205700 KB	Output is correct
2	Runtime error	498 ms	417248 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	205700 KB	Output is correct
2	Runtime error	498 ms	417248 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	205704 KB	Output is correct
2	Correct	85 ms	205712 KB	Output is correct
3	Correct	95 ms	205696 KB	Output is correct
4	Correct	98 ms	205760 KB	Output is correct
5	Correct	309 ms	205796 KB	Output is correct
6	Correct	542 ms	205792 KB	Output is correct
7	Correct	148 ms	205680 KB	Output is correct
8	Correct	408 ms	205796 KB	Output is correct
9	Correct	970 ms	205800 KB	Output is correct
10	Correct	80 ms	205732 KB	Output is correct
11	Correct	101 ms	205788 KB	Output is correct
12	Correct	78 ms	205700 KB	Output is correct
13	Runtime error	498 ms	417248 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	205700 KB	Output is correct
2	Runtime error	498 ms	417248 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	205704 KB	Output is correct
2	Correct	85 ms	205712 KB	Output is correct
3	Correct	95 ms	205696 KB	Output is correct
4	Correct	98 ms	205760 KB	Output is correct
5	Correct	309 ms	205796 KB	Output is correct
6	Correct	542 ms	205792 KB	Output is correct
7	Correct	148 ms	205680 KB	Output is correct
8	Correct	408 ms	205796 KB	Output is correct
9	Correct	970 ms	205800 KB	Output is correct
10	Correct	80 ms	205732 KB	Output is correct
11	Correct	101 ms	205788 KB	Output is correct
12	Correct	101 ms	205732 KB	Output is correct
13	Correct	82 ms	205764 KB	Output is correct
14	Correct	81 ms	205748 KB	Output is correct
15	Correct	77 ms	205728 KB	Output is correct
16	Correct	261 ms	205800 KB	Output is correct
17	Correct	467 ms	205800 KB	Output is correct
18	Correct	120 ms	205708 KB	Output is correct
19	Correct	350 ms	205716 KB	Output is correct
20	Correct	778 ms	205696 KB	Output is correct
21	Correct	77 ms	205792 KB	Output is correct
22	Correct	78 ms	205716 KB	Output is correct
23	Runtime error	262 ms	417188 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	205700 KB	Output is correct
2	Runtime error	498 ms	417248 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	205704 KB	Output is correct
2	Correct	85 ms	205712 KB	Output is correct
3	Correct	95 ms	205696 KB	Output is correct
4	Correct	98 ms	205760 KB	Output is correct
5	Correct	309 ms	205796 KB	Output is correct
6	Correct	542 ms	205792 KB	Output is correct
7	Correct	148 ms	205680 KB	Output is correct
8	Correct	408 ms	205796 KB	Output is correct
9	Correct	970 ms	205800 KB	Output is correct
10	Correct	80 ms	205732 KB	Output is correct
11	Correct	101 ms	205788 KB	Output is correct
12	Correct	101 ms	205732 KB	Output is correct
13	Correct	82 ms	205764 KB	Output is correct
14	Correct	81 ms	205748 KB	Output is correct
15	Correct	77 ms	205728 KB	Output is correct
16	Correct	261 ms	205800 KB	Output is correct
17	Correct	467 ms	205800 KB	Output is correct
18	Correct	120 ms	205708 KB	Output is correct
19	Correct	350 ms	205716 KB	Output is correct
20	Correct	778 ms	205696 KB	Output is correct
21	Correct	77 ms	205792 KB	Output is correct
22	Correct	78 ms	205716 KB	Output is correct
23	Runtime error	262 ms	417188 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Submission #573078

Compilation message