oj.uz

Submission #47618

# Submission time Handle Problem Language Result Execution time Memory
47618 2018-05-05T21:22:48 Z IvanC Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 251 ms 21660 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> S1,S2,V1,V2;
ll N,M,ptr,A,B,tot;

void brute1(ll val,int pos){
	if(pos == A){
		S1.push_back(val);
		return;
	}
	brute1(val + V1[pos],pos+1);
	brute1(val,pos+1);
}

void brute2(ll val,int pos){
	if(pos == B){
		S2.push_back(val);
		return;
	}
	brute2(val + V2[pos],pos+1);
	brute2(val,pos+1);
}

int main(){
	cin >> N >> M;
	for(int i = 0;i<N;i++){
		ll x;
		cin >> x;
		if(i & 1) V1.push_back(x);
		else V2.push_back(x);
	}
	A = V1.size();
	brute1(0,0);
	sort(S1.begin(),S1.end());
	//for(ll i : S1) cout << " " << i;
	//cout << endl;
	B = V2.size();
	brute2(0,0);
	sort(S2.rbegin(),S2.rend());
	//for(ll i : S2) cout << " " << i;
	//cout << endl;
	for(int i = 0;i<S1.size();i++){
		//printf("S1[%d] %lld S2[%lld] %lld\n",i,S1[i],ptr,S2[ptr]);
		if(S1[i] > M) break;
		while(S1[i] + S2[ptr] > M){
			ptr++;
			//printf("S1[%d] %lld S2[%lld] %lld\n",i,S1[i],ptr,S2[ptr]);
		}
		tot += S2.size() - ptr;
	}
	cout << tot << endl;
	return 0;
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S1.size();i++){
                ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 712 KB Output is correct
7 Correct 2 ms 712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 816 KB Output is correct
2 Correct 2 ms 816 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 856 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2604 KB Output is correct
2 Correct 60 ms 6052 KB Output is correct
3 Correct 244 ms 21400 KB Output is correct
4 Correct 58 ms 21400 KB Output is correct
5 Correct 9 ms 21400 KB Output is correct
6 Correct 8 ms 21400 KB Output is correct
7 Correct 14 ms 21400 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21400 KB Output is correct
2 Correct 21 ms 21400 KB Output is correct
3 Correct 94 ms 21400 KB Output is correct
4 Correct 2 ms 21400 KB Output is correct
5 Correct 5 ms 21400 KB Output is correct
6 Correct 14 ms 21400 KB Output is correct
7 Correct 14 ms 21400 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 21400 KB Output is correct
2 Correct 89 ms 21400 KB Output is correct
3 Correct 89 ms 21400 KB Output is correct
4 Correct 2 ms 21400 KB Output is correct
5 Correct 42 ms 21400 KB Output is correct
6 Correct 209 ms 21528 KB Output is correct
7 Correct 84 ms 21528 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 21528 KB Output is correct
2 Correct 21 ms 21528 KB Output is correct
3 Correct 8 ms 21528 KB Output is correct
4 Correct 2 ms 21528 KB Output is correct
5 Correct 6 ms 21528 KB Output is correct
6 Correct 178 ms 21528 KB Output is correct
7 Correct 14 ms 21528 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21528 KB Output is correct
2 Correct 57 ms 21528 KB Output is correct
3 Correct 8 ms 21528 KB Output is correct
4 Correct 8 ms 21528 KB Output is correct
5 Correct 49 ms 21528 KB Output is correct
6 Correct 20 ms 21528 KB Output is correct
7 Correct 246 ms 21592 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 21660 KB Output is correct
2 Correct 21 ms 21660 KB Output is correct
3 Correct 9 ms 21660 KB Output is correct
4 Correct 251 ms 21660 KB Output is correct
5 Correct 63 ms 21660 KB Output is correct
6 Correct 14 ms 21660 KB Output is correct
7 Correct 29 ms 21660 KB Output is correct