oj.uz

Submission #37342

# Submission time Handle Problem Language Result Execution time Memory
37342 2017-12-24T12:33:40 Z IvanC San (COCI17_san) C++14
48 / 120
 1000 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 42;
vector<int> compressao;
int H1[MAXN],H2[MAXN],NT,N,M;
vector<ll> possiveis[MAXN];
ll G1[MAXN],G2[MAXN],K,resposta;
int main(){
	cin >> NT >> K;
	N = NT;
	M = 0;
	compressao.push_back(0);
	for(int i = 1;i<=N;i++){
		cin >> H1[i] >> G1[i];
		compressao.push_back(H1[i]);
	}
	for(int i = 1;i<=M;i++){
		cin >> H2[i] >> G2[i];
		compressao.push_back(H2[i]);
	}
	sort(compressao.begin(),compressao.end());
	compressao.erase(unique(compressao.begin(),compressao.end()),compressao.end());
	for(int i = 1;i<=N;i++){
		H1[i] = lower_bound(compressao.begin(),compressao.end(),H1[i]) - compressao.begin();
	}
	for(int i = 1;i<=M;i++){
		H2[i] = lower_bound(compressao.begin(),compressao.end(),H2[i]) - compressao.begin();
	}
	for(ll bitmask = 1;bitmask < (1LL << N);bitmask++){
		int last = 0;
		ll total = 0;
		bool flag = false;
		for(int i = 0;i<N;i++){
			if(bitmask & (1LL << i)){
				int j = i + 1;
				if(H1[last] > H1[j]) flag = true;
				last = j;
				total += G1[j];
			}
		}
		if(flag) continue;
		possiveis[H1[last]].push_back(total);
		if(total >= K) resposta++;
	}
	for(int bitmask = 1;bitmask < (1 << M);bitmask++){
		int last = 0;
		int first = 0;
		ll total = 0;
		bool flag = false;
		for(int i = 0;i<M;i++){
			if(bitmask & (1 << i)){
				int j = i + 1;
				if(H2[last] > H2[j]) flag = true;
				if(first == 0) first = j;
				last = j;
				total += G2[j];
			}
		}
		if(flag) continue;
		if(total >= K) resposta++;
		for(int i = 0;i<=H2[first];i++){
			resposta += possiveis[i].end() - lower_bound(possiveis[i].begin(),possiveis[i].end(),K - total);
		}
	}
	cout << resposta << endl;
	return 0;
}

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5188 KB Output is correct
2 Correct 89 ms 2164 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 576 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 43284 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 65536 KB Execution timed out
2 Halted 0 ms 0 KB -