답안 #757960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757960	2023-06-14T02:52:30 Z	ProtonDecay314	Gym Badges (NOI22_gymbadges)	C++17	24 / 100	430 ms	12248 KB

Main

/*
Guess who has a bitmask dp solution
that will work on the first subtask?
Heh, that's right, STARLIGHT ANYA

Also, subtask 2 is cute because you just sort the gyms by X_i
and then find the longest prefix of X that works

All in all, 24 points ^^

I will O(n^2) later ^^
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> x;
vector<ll> l;
ll n;
bool memo[1 << 10] = {false};
bool solved[1 << 10] = {false};
bool poss(int S) {
    bool& ans = memo[S];

    if(!solved[S]) {
        if(S == 0) {
            ans = true;
            return ans;
        }
        ans = false;
        ll sumx = 0;
        for(int i = 0; i < 10; i++) {
            sumx += ((S >> i) & 1 ? x[i] : 0);
        }

        for(int i = 0; i < 10; i++) {
            if((S >> i) & 1) {
                if(poss(S ^ (1 << i)) && (sumx - x[i]) <= l[i]) {
                    ans = true;
                    break;
                }
            }
        }
    }
    solved[S] = true;
    return ans;
}

ll subtask2_solve(vector<ll> x, ll l) {
    sort(x.begin(), x.end());

    ll sum = 0ll;
    ll i = 0ll;
    ll n = x.size();
    while(i < n && sum <= l) {
        sum += x[i];
        i++;
    }
    return i;
}

int main() {
    cin >> n;

    for(ll i = 0ll; i < n; i++) {
        ll cur;
        cin >> cur;
        x.push_back(cur);
    }

    for(ll i = 0ll; i < n; i++) {
        ll cur;
        cin >> cur;
        l.push_back(cur);
    }

    if(n <= 10) {
        poss((1 << n) - 1);

        int ans = 0;

        for(int i = 0; i < (1 << 10); i++) {
            if(memo[i]) {
                ans = max(ans, __popcount(i));
            }
        }

        cout << ans;
    } else {
        // Assume subtask 2 constraints
        cout << subtask2_solve(x, l[0]) << endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	12128 KB	Output is correct
2	Correct	395 ms	12032 KB	Output is correct
3	Correct	430 ms	12184 KB	Output is correct
4	Correct	404 ms	12064 KB	Output is correct
5	Correct	382 ms	12048 KB	Output is correct
6	Correct	380 ms	12184 KB	Output is correct
7	Correct	377 ms	12172 KB	Output is correct
8	Correct	373 ms	12052 KB	Output is correct
9	Correct	361 ms	12040 KB	Output is correct
10	Correct	387 ms	12108 KB	Output is correct
11	Correct	324 ms	12152 KB	Output is correct
12	Correct	361 ms	12180 KB	Output is correct
13	Correct	337 ms	12108 KB	Output is correct
14	Correct	373 ms	12104 KB	Output is correct
15	Correct	349 ms	12248 KB	Output is correct
16	Correct	355 ms	12092 KB	Output is correct
17	Correct	353 ms	12196 KB	Output is correct
18	Correct	358 ms	12232 KB	Output is correct
19	Correct	362 ms	12148 KB	Output is correct
20	Correct	361 ms	12024 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Incorrect	4 ms	340 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	408 ms	12128 KB	Output is correct
22	Correct	395 ms	12032 KB	Output is correct
23	Correct	430 ms	12184 KB	Output is correct
24	Correct	404 ms	12064 KB	Output is correct
25	Correct	382 ms	12048 KB	Output is correct
26	Correct	380 ms	12184 KB	Output is correct
27	Correct	377 ms	12172 KB	Output is correct
28	Correct	373 ms	12052 KB	Output is correct
29	Correct	361 ms	12040 KB	Output is correct
30	Correct	387 ms	12108 KB	Output is correct
31	Correct	324 ms	12152 KB	Output is correct
32	Correct	361 ms	12180 KB	Output is correct
33	Correct	337 ms	12108 KB	Output is correct
34	Correct	373 ms	12104 KB	Output is correct
35	Correct	349 ms	12248 KB	Output is correct
36	Correct	355 ms	12092 KB	Output is correct
37	Correct	353 ms	12196 KB	Output is correct
38	Correct	358 ms	12232 KB	Output is correct
39	Correct	362 ms	12148 KB	Output is correct
40	Correct	361 ms	12024 KB	Output is correct
41	Incorrect	4 ms	340 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #757960

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 9.0 / 9.0

Subtask #3 0 / 27.0

Subtask #4 0 / 49.0

Subtask #1
15.0 / 15.0

Subtask #2
9.0 / 9.0

Subtask #3
0 / 27.0

Subtask #4
0 / 49.0