Submission #394128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394128	2021-04-25T17:41:10 Z	Lobo	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	568 ms	20776 KB

bobek

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll =  1000000000000000000;
const int INFii = 1000000000;
const long long mod = (long long) 1e9 + 7;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define S second
#define F first
#define MP make_pair
#define PB push_back

#define maxn 

ll n, m, n1, n2, ans;
vector<ll> a1, a2, l1, l2;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("____.out", "w", stdout);

    cin >> n >> m;

    n2 = n/2;
    n1 = n - n2;
    
    for(ll i = 0; i < n1; i++) {
        ll c;
        cin >> c;
        a1.PB(c);
    }

    for(ll i = 0; i < n1; i++) {
        ll c;
        cin >> c;
        a2.PB(c);
    }


    for(ll mask = 0; mask < (1<<n1); mask++) {
        ll sum = 0;

        for(ll i = 0; i < n1; i++)
            if((mask&(1<<i)) != 0)
                sum+= a1[i];
            
        l1.PB(sum);
    }

    for(ll mask = 0; mask < (1<<n2); mask++) {
        ll sum = 0;

        for(ll i = 0; i < n2; i++)
            if((mask&(1<<i)) != 0)
                sum+= a2[i];
            
        l2.PB(sum);
    }

    sort(l2.begin(),l2.end());

    for(auto a : l1) {
        ans+= upper_bound(l2.begin(),l2.end(),m-a) - l2.begin();
    }

    cout << ans << endl;
    return 0;

}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	2332 KB	Output is correct
2	Correct	110 ms	5416 KB	Output is correct
3	Correct	568 ms	20768 KB	Output is correct
4	Correct	107 ms	5340 KB	Output is correct
5	Correct	15 ms	1612 KB	Output is correct
6	Correct	9 ms	976 KB	Output is correct
7	Correct	15 ms	1612 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	2888 KB	Output is correct
2	Correct	36 ms	2248 KB	Output is correct
3	Correct	202 ms	10480 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	7 ms	976 KB	Output is correct
6	Correct	15 ms	1616 KB	Output is correct
7	Correct	18 ms	1540 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	4416 KB	Output is correct
2	Correct	170 ms	8476 KB	Output is correct
3	Correct	179 ms	8500 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	97 ms	8496 KB	Output is correct
6	Correct	274 ms	20772 KB	Output is correct
7	Correct	96 ms	8496 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	364 ms	16724 KB	Output is correct
2	Correct	33 ms	2376 KB	Output is correct
3	Correct	12 ms	976 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	7 ms	960 KB	Output is correct
6	Correct	192 ms	16676 KB	Output is correct
7	Correct	16 ms	1552 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	2380 KB	Output is correct
2	Correct	99 ms	5332 KB	Output is correct
3	Correct	12 ms	960 KB	Output is correct
4	Correct	10 ms	976 KB	Output is correct
5	Correct	106 ms	8556 KB	Output is correct
6	Correct	24 ms	2376 KB	Output is correct
7	Correct	335 ms	20776 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	419 ms	20716 KB	Output is correct
2	Correct	41 ms	2376 KB	Output is correct
3	Correct	11 ms	976 KB	Output is correct
4	Correct	559 ms	20776 KB	Output is correct
5	Correct	126 ms	10460 KB	Output is correct
6	Correct	16 ms	1612 KB	Output is correct
7	Correct	33 ms	2888 KB	Output is correct

Submission #394128

Compilation message