Submission #116884

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116884	2019-06-14T03:28:39 Z	JohnTitor	Ice Hockey World Championship (CEOI15_bobek)	C++11	100 / 100	406 ms	8812 KB

bobek

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Hockey"
int n;
ll m;
ll a[40];
vector <ll> cost;
void backtrack(int u, ll c){
    if(u==n||u==20){
        cost.pb(c);
    }
    else{
        backtrack(u+1, c);
        if(c+a[u]<=m) backtrack(u+1, c+a[u]);
    }
}
ll ans=0;
void backtrack2(int u, ll c){
    if(u>=n){
        ans+=upper_bound(cost.begin(), cost.end(), m-c)-cost.begin();
    }
    else{
        backtrack2(u+1, c);
        if(c+a[u]<=m) backtrack2(u+1, c+a[u]);
    }
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(m);
    FFOR(i, 0, n) read(a[i]);
    backtrack(0, 0);
    sort(cost.begin(), cost.end());
    backtrack2(20, 0);
    writeln(ans);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1528 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	7 ms	1020 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	5 ms	1020 KB	Output is correct
6	Correct	102 ms	8684 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	8684 KB	Output is correct
2	Correct	7 ms	1020 KB	Output is correct
3	Correct	6 ms	1020 KB	Output is correct
4	Correct	4 ms	512 KB	Output is correct
5	Correct	25 ms	4592 KB	Output is correct
6	Correct	14 ms	1528 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	8684 KB	Output is correct
2	Correct	117 ms	8684 KB	Output is correct
3	Correct	336 ms	8684 KB	Output is correct
4	Correct	115 ms	8684 KB	Output is correct
5	Correct	56 ms	8684 KB	Output is correct
6	Correct	80 ms	8684 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	8684 KB	Output is correct
2	Correct	96 ms	8732 KB	Output is correct
3	Correct	147 ms	8684 KB	Output is correct
4	Correct	2 ms	428 KB	Output is correct
5	Correct	51 ms	8684 KB	Output is correct
6	Correct	95 ms	8720 KB	Output is correct
7	Correct	2 ms	356 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	8696 KB	Output is correct
2	Correct	131 ms	8704 KB	Output is correct
3	Correct	125 ms	8668 KB	Output is correct
4	Correct	17 ms	2572 KB	Output is correct
5	Correct	57 ms	8684 KB	Output is correct
6	Correct	121 ms	8684 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	217 ms	8808 KB	Output is correct
2	Correct	100 ms	8656 KB	Output is correct
3	Correct	95 ms	8684 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	61 ms	8684 KB	Output is correct
6	Correct	132 ms	8684 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	104 ms	8684 KB	Output is correct
2	Correct	124 ms	8708 KB	Output is correct
3	Correct	110 ms	8684 KB	Output is correct
4	Correct	87 ms	8684 KB	Output is correct
5	Correct	67 ms	8684 KB	Output is correct
6	Correct	103 ms	8684 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	295 ms	8684 KB	Output is correct
2	Correct	106 ms	8684 KB	Output is correct
3	Correct	112 ms	8812 KB	Output is correct
4	Correct	406 ms	8684 KB	Output is correct
5	Correct	77 ms	8684 KB	Output is correct
6	Correct	106 ms	8668 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct

Submission #116884

Compilation message