Submission #80022

#	Time	Username	Problem	Language	Result	Execution time	Memory
80022		pzdba	San (COCI17_san)	C++14	120 / 120	272 ms	3116 KiB

san

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL h[45], g[45];
vector<LL> dp[25];
int main(){
	int n;
	LL k;
	scanf("%d%lld", &n, &k);
	for(int i=0;i<n;i++){
		scanf("%lld%lld", &h[i], &g[i]);
	}
	if(n == 1){
		if(g[1] >= k) printf("1\n");
		else printf("0\n");
		return 0;
	}
	int mid1 = n/2;
	LL ans = 0;
	for(int i=1;i<(1<<mid1);i++){
		int mx = 0, last = -1;
		LL sum = 0;
		bool ok = 1;
		for(int j=0;j<mid1;j++){
			if((i>>j)&1){
				if(h[j] < mx){
					ok = 0;
					break;
				}
				mx = h[j];
				last = j;
				sum += g[j];
			}
		}
		if(!ok) continue;
		dp[last].emplace_back(sum);
		if(sum >= k) ans++;
	}
	for(int i=0;i<mid1;i++) sort(dp[i].begin(), dp[i].end());
	int mid2 = n - mid1;
	for(int i=1;i<(1<<mid2);i++){
		int mx = 0, last = -1;
		LL sum = 0;
		bool ok = 1;
		for(int j=0;j<mid2;j++){
			if((i>>j)&1){
				if(h[j+mid1] < mx){
					ok = 0;
					break;
				}
				mx = h[j+mid1];
				if(last == -1) last = j+mid1;
				sum += g[j+mid1];
			}
		}
		if(!ok) continue;
		for(int j=0;j<mid1;j++){
			if(h[last] >= h[j]){
				int idx = lower_bound(dp[j].begin(), dp[j].end(), k-sum) - dp[j].begin();
				ans += dp[j].size() - idx;
			}
		}
		if(sum >= k) ans++;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:9: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:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &h[i], &g[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24