oj.uz

Submission #146813

# Submission time Handle Problem Language Result Execution time Memory
146813 2019-08-26T09:19:26 Z algorithm16 San (COCI17_san) C++14
120 / 120
 156 ms 2788 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include <assert.h>
using namespace std;
typedef long long int llint;
llint n,k,sol;
pair <llint,llint> p[45];
vector <llint> m[25];
vector <llint> v;
vector <llint> v2;
void rek(llint ind,llint x,llint poc) {
	if(ind>=n/2) return;
	if(x>0) m[lower_bound(v.begin(),v.end(),p[ind].first)-v.begin()].push_back(x);
	llint c=n/2;
	for(llint i=ind+1;i<c;i++) {
		if(ind==-1) rek(i,x+p[i].second,p[i].first);
		else if(p[i].first>=p[ind].first) rek(i,x+p[i].second,poc);
	}
}
void rek2(llint ind,llint x,llint poc) {
	//cout << ind << " " << x << " " << poc << endl;
	if(ind>=n) return;
	if(ind>=n/2) {
		//cout << ind << " " << x << " " << poc << endl;
		if(x>=k) sol+=1;
		llint ind1=lower_bound(v.begin(),v.end(),poc+1)-v.begin();
		//if(p[ind1].first==poc) ind1+=1;
		for(llint i=0;i<ind1;i++) {
			sol+=m[i].size()-(lower_bound(m[i].begin(),m[i].end(),k-x)-m[i].begin());
			//cout << v[i] << " " << sol << endl;
		}
	}
	for(llint i=ind+1;i<n;i++) {
		//cout << i << " " << p[i].first << endl;
		if(ind==n/2-1) rek2(i,x+p[i].second,p[i].first);
		else if(p[i].first>=p[ind].first) rek2(i,x+p[i].second,poc);
	}
}
int main()
{
	cin >> n >> k;
	for(llint i=0;i<n;i++) {
		cin >> p[i].first >> p[i].second;
		if(i<n/2) v.push_back(p[i].first);
		//if(p[i].second>=k) sol+=1;
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	rek(-1,0,0);
	for(llint i=0;i<v.size();i++) {
		sort(m[i].begin(),m[i].end());
	}
	for(llint i=0;i<v.size();i++) {
		v2.push_back(v[i]);
		//cout << v[i] << endl;
		for(llint j=0;j<m[i].size();j++) {
			//cout << m[i][j] << " ";
			if(m[i][j]>=k) sol+=1;
		}
		//cout << endl;
	}
	rek2(n/2-1,0,0);
	cout << sol;
	return 0;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llint i=0;i<v.size();i++) {
                ~^~~~~~~~~
san.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llint i=0;i<v.size();i++) {
                ~^~~~~~~~~
san.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llint j=0;j<m[i].size();j++) {
                 ~^~~~~~~~~~~~

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1080 KB Output is correct
2 Correct 5 ms 632 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 2788 KB Output is correct
2 Correct 20 ms 1484 KB Output is correct