Submission #473524

#TimeUsernameProblemLanguageResultExecution timeMemory
473524_L__San (COCI17_san)C++17
0 / 120
1094 ms14572 KiB
// This code is written by _L__ #include <bits/stdc++.h> using namespace std; #define endl '\n' #define F_word ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); typedef long long ll; typedef long double ld; const ll mod = 1e9+7, N = 5e5+13, inf = 1e9+1; const ld E = 1e-6; #define ff first #define ss second int main(void){ F_word; ll n, k; cin >> n >> k; ll h[n] = {}, c[n]= {}; ll ans = 0; int x = n/2; int b = (n-(n/2)); for(int i = 0; i < n; ++i) cin >> h[i] >> c[i]; vector<pair<ll, ll>> fbi; for(int i = 0; i < (1<<x); ++i){ ll hg = 0, gg = 0; for(int j = 0; j < x; ++j){ if(i&(1<<j)){ if(hg <= h[j]){hg = h[j], gg += c[j];} else break; } } fbi.push_back({hg, gg}); ans += (gg >= k); } //for(auto u: fbi) cout << u.ff << ' ' << u.ss << endl; map<ll, vector<ll>> mp; for(int i = 0; i < (1<<b); ++i){ ll hg = 0, gg = 0; for(int j = 0; j < b; ++j){ if(i&(1<<j)){ if(hg <= h[j+x]){hg = h[j+x]; gg += c[j+x];} else {gg = -1; break;} } } if(gg == -1) continue; for(int j = 0; j < b; ++j){ if(i&(1<<j)){ mp[h[j+x]].push_back(gg); break; } } } for(auto i: mp)sort(i.ss.begin(), i.ss.end()); for(auto u: fbi){ for(auto i: mp){ if(i.ff >= u.ff){ ll f = lower_bound(i.ss.begin(), i.ss.end(), k-u.ss)-i.ss.begin(); ans += i.ss.size()-f; } } } cout << ans << endl; }
#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...