oj.uz

Submission #82342

# Submission time Handle Problem Language Result Execution time Memory
82342 2018-10-30T07:14:53 Z farukkastamonuda San (COCI17_san) C++14
120 / 120
 183 ms 9140 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
using namespace std;
int n;
lo int k;
pair<lo int,lo int> p[45];
vector< pair<int,lo int> > v;
vector<lo int> v1[45];
void calc1(int sira,lo int sum,int fin,int heig){
	if(sira==fin){
		if(heig)
			v.pb(mp(heig,sum));
		return ;
	}
	calc1(sira+1,sum,fin,heig);
	if(p[sira].fi>=heig) calc1(sira+1,sum+p[sira].se,fin,p[sira].fi);
}
void calc2(int sira,lo int sum,int fin,int heig,int ind){
	if(sira==fin){
		v1[ind].pb(sum);
		return ;
	}
	calc2(sira+1,sum,fin,heig,ind);
	if(p[sira].fi>=heig) 
		calc2(sira+1,sum+p[sira].se,fin,p[sira].fi,ind);
}
int main(){
	scanf("%d %lld",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%lld %lld",&p[i].fi,&p[i].se);
	}
	calc1(0,0,n/2,0);
	for(int i=n/2;i<n;i++){
		calc2(i+1,p[i].se,n,p[i].fi,i);
	}
	lo int ans=0;
	for(int i=n/2;i<n;i++){
		sort(v1[i].begin(),v1[i].end());
		for(int j=0;j<(int)v1[i].size();j++){
			if(v1[i][j]>=k) ans++;
		}
	}
	for(int i=0;i<(int)v.size();i++){
		lo int h=v[i].fi,sm=v[i].se;
		if(sm>=k) ans++;
		for(int j=n/2;j<n;j++){
			if(p[j].fi<h) continue;
			if(lower_bound(v1[j].begin(),v1[j].end(),k-sm)==v1[j].end()) continue;
			ans+=(int)v1[j].size()-(lower_bound(v1[j].begin(),v1[j].end(),k-sm)-v1[j].begin());
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~~
san.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&p[i].fi,&p[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1872 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2572 KB Output is correct
2 Correct 7 ms 2572 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9140 KB Output is correct
2 Correct 30 ms 9140 KB Output is correct