oj.uz

Submission #80022

# Submission time Handle Problem Language Result Execution time Memory
80022 2018-10-18T09:30:15 Z pzdba San (COCI17_san) C++14
120 / 120
 272 ms 3116 KB 
#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

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.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1120 KB Output is correct
2 Correct 5 ms 1120 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1400 KB Output is correct
2 Correct 21 ms 1400 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 3116 KB Output is correct
2 Correct 119 ms 3116 KB Output is correct