oj.uz

Submission #524053

# Submission time Handle Problem Language Result Execution time Memory
524053 2022-02-08T14:48:21 Z tube5429 San (COCI17_san) C++14
120 / 120
 115 ms 7576 KB 
#include<bits/stdc++.h>
using namespace std;

#define sz(v) (int)(v).size()

typedef long long ll;
const int MX = 42;

int N, h[MX], g[MX];
ll K;

vector<int> hs;
vector<ll> L[MX], R[MX];
void rec_left(int pos, int last, ll sum) {
	if(pos == N/2) {
		int idx = lower_bound(hs.begin(), hs.end(), last) - hs.begin();
		L[idx].push_back(sum);
		return;
	}
	rec_left(pos+1, last, sum);
	if(h[pos] >= last) {
		rec_left(pos+1, h[pos], sum + g[pos]);
	}
}

void rec_right(int pos, int first, int last, ll sum) {
	if(pos == N) {
		int idx = lower_bound(hs.begin(), hs.end(), first) - hs.begin();
		R[idx].push_back(sum);
		return;
	}
	rec_right(pos+1, first, last, sum);
	if(h[pos] >= last) {
		int nfirst = (first == 0) ? h[pos] : first;
		rec_right(pos+1, nfirst, h[pos], sum + g[pos]);
	}
}

int main() {
	cin>>N>>K;
	for(int i = 0 ; i<N ; i++) {
		cin>>h[i]>>g[i];
		hs.push_back(h[i]);
	}
	hs.push_back(0);
	sort(hs.begin(), hs.end());
	rec_left(0, 0, 0);
	rec_right(N/2, 0, 0, 0);
	ll ans = 0;
	for(int i = 0; i<sz(hs) ; i++) {
		sort(R[i].begin(), R[i].end());
	}
	for(int i = 0 ; i<sz(hs) ; i++) {
		for(auto it : L[i]) {
			ans += R[0].end() - lower_bound(R[0].begin(), R[0].end(), K - it);
			for(int j = i; j<sz(hs); j++) {
				ans += R[j].end() - lower_bound(R[j].begin(), R[j].end(), K - it);
			}
		}
	}
	cout << ans << "\n";

	return 0;
}

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1092 KB Output is correct
2 Correct 1 ms 284 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1996 KB Output is correct
2 Correct 4 ms 460 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 7576 KB Output is correct
2 Correct 20 ms 1580 KB Output is correct