Submission #320047

#TimeUsernameProblemLanguageResultExecution timeMemory
320047gustasonSan (COCI17_san)C++14
120 / 120
190 ms7768 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxN = 45; vector<ll> L[maxN]; vector<ll> R[maxN]; ll h[maxN], c[maxN], n, k; vector<int> hs; void rec_left(int pos, int last, ll sum) { if (pos == n/2) { auto 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 + c[pos]); } } void rec_right(int pos, int first, int last, ll sum) { if (pos == n) { auto 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) { if (first == 0) { first = h[pos]; } rec_right(pos + 1, first, h[pos], sum + c[pos]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for(int i = 0; i < n; i++) { cin >> h[i] >> c[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); for(int i = 0; i < (int) hs.size(); i++) { sort(L[i].begin(), L[i].end()); sort(R[i].begin(), R[i].end()); } ll ans = 0; for(int i = 0; i < (int) hs.size(); 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 < (int) hs.size(); j++) { ans += R[j].end() - lower_bound(R[j].begin(), R[j].end(), k - it); } } } cout << ans << "\n"; return 0; } //~ check for overflows
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...