oj.uz

Submission #49965

# Submission time Handle Problem Language Result Execution time Memory
49965 2018-06-05T15:03:42 Z faishol27 Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 679 ms 21536 KB 
////////////////////////////////////////////////
//                                            //
//  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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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