답안 #49965 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49965	2018-06-05T15:03:42 Z	faishol27	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	679 ms	21536 KB

bobek

////////////////////////////////////////////////
//                                            //
//  Author: Muhammad Faishol Amirul Mukminin  //
//                                            //
////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<pi,int> pii;
typedef pair<ll,ll> pl;
typedef pair<pl,ll> pll;
typedef pair<double,double> pd;
typedef pair<pd,double> pdd;

#define FOR(i,x,y) for(int i=(x);i<(y);i++)
#define FORN(i,x,y) for(int i=(x);i<=(y);i++)
#define REV(i,a,b) for(int i=(a);i>(b);i--)
#define REVN(i,a,b) for(int i=(a);i>=(b);i--)
#define BTW(i,a,b) a <= i && i <= b

#define DB(x) cerr << #x << ": " << x << endl;

#define fi first
#define se second
#define PUB push_back
#define POB pop_back
#define PUF push_front
#define POF pop_front
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"

const double EPS = 1e-9;
const double PI = acos(-1);
const ll MOD = 1e9+7;
const int INF = 0x7FFFFFFF;
const ll LINF = 0x7FFFFFFFFFFFFFFFLL;
const ull UINF = 0xFFFFFFFFFFFFFFFFLL;
const int dCol[] = {0,+1,0,-1,+1,+1,-1,-1};
const int dRow[] = {-1,0,+1,0,-1,+1,+1,-1};

template <typename T>
inline void VIN(vector<T> &i){ T x; cin >> x; i.PUB(x); }
inline void FIO(string i){ freopen((i+".in").c_str(), "r", stdin); freopen((i+".out").c_str(), "w", stdout);}

int N;
ll M, ans = 0, tiket[43];
vector<ll>bayar[2];

void solve(int id, int awal, int fin){
	int pjg = fin-awal;
	FORN(i,0,pjg){
		vector<bool>stt(pjg-i,0);
		stt.resize(pjg,1);

		do{
			ll tmp = 0;

			FOR(i,0,pjg){
				if(stt[i])
					tmp += tiket[awal+i];
			}

			bayar[id].PUB(tmp);
		}while(next_permutation(stt.begin(), stt.end()));
	}
}

int binser(ll s){
	int ret = -1;
	int l = 0, r = bayar[1].size()-1;
	
	while(l <= r){
		int m = (l+r)/2;

		if(bayar[1][m] > s) r = m-1;
		else{
			ret = max(ret, m);
			l = m+1;
		}
	}

	return ret;
}

int main(){
#ifndef LOCAL

#endif

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N >> M;
	FOR(i,0,N) cin >> tiket[i];
	
	solve(0,0,N/2);
	solve(1,N/2,N);
	
	FOR(i,0,2) sort(bayar[i].begin(), bayar[i].end());
	
    for(ll elm:bayar[0]){
		if(elm > M) break;
		ans += binser(M-elm)+1;
	}

	cout << ans << endl;
	
	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	500 KB	Output is correct
2	Correct	2 ms	500 KB	Output is correct
3	Correct	2 ms	500 KB	Output is correct
4	Correct	2 ms	500 KB	Output is correct
5	Correct	3 ms	524 KB	Output is correct
6	Correct	3 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	652 KB	Output is correct
2	Correct	3 ms	652 KB	Output is correct
3	Correct	2 ms	700 KB	Output is correct
4	Correct	3 ms	704 KB	Output is correct
5	Correct	3 ms	712 KB	Output is correct
6	Correct	2 ms	716 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	720 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	744 KB	Output is correct
4	Correct	3 ms	748 KB	Output is correct
5	Correct	3 ms	764 KB	Output is correct
6	Correct	4 ms	764 KB	Output is correct
7	Correct	2 ms	764 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	2424 KB	Output is correct
2	Correct	126 ms	5872 KB	Output is correct
3	Correct	564 ms	21388 KB	Output is correct
4	Correct	131 ms	21388 KB	Output is correct
5	Correct	28 ms	21388 KB	Output is correct
6	Correct	17 ms	21388 KB	Output is correct
7	Correct	28 ms	21388 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	21388 KB	Output is correct
2	Correct	50 ms	21388 KB	Output is correct
3	Correct	235 ms	21388 KB	Output is correct
4	Correct	2 ms	21388 KB	Output is correct
5	Correct	13 ms	21388 KB	Output is correct
6	Correct	31 ms	21388 KB	Output is correct
7	Correct	28 ms	21388 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	91 ms	21388 KB	Output is correct
2	Correct	188 ms	21388 KB	Output is correct
3	Correct	197 ms	21388 KB	Output is correct
4	Correct	2 ms	21388 KB	Output is correct
5	Correct	156 ms	21388 KB	Output is correct
6	Correct	468 ms	21408 KB	Output is correct
7	Correct	180 ms	21408 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	412 ms	21408 KB	Output is correct
2	Correct	65 ms	21408 KB	Output is correct
3	Correct	16 ms	21408 KB	Output is correct
4	Correct	5 ms	21408 KB	Output is correct
5	Correct	14 ms	21408 KB	Output is correct
6	Correct	374 ms	21408 KB	Output is correct
7	Correct	31 ms	21408 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	21408 KB	Output is correct
2	Correct	130 ms	21408 KB	Output is correct
3	Correct	18 ms	21408 KB	Output is correct
4	Correct	17 ms	21408 KB	Output is correct
5	Correct	136 ms	21408 KB	Output is correct
6	Correct	44 ms	21408 KB	Output is correct
7	Correct	456 ms	21436 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	535 ms	21536 KB	Output is correct
2	Correct	48 ms	21536 KB	Output is correct
3	Correct	21 ms	21536 KB	Output is correct
4	Correct	679 ms	21536 KB	Output is correct
5	Correct	195 ms	21536 KB	Output is correct
6	Correct	36 ms	21536 KB	Output is correct
7	Correct	57 ms	21536 KB	Output is correct

답안 #49965

Compilation message