Submission #474075

#TimeUsernameProblemLanguageResultExecution timeMemory
474075_L__San (COCI17_san)C++17
0 / 120
1087 ms10640 KiB
// This code is written by _L__ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>; #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 = 1e11; const ld E = 1e-6; #define ff first #define ss second int main(void){ F_word; ll n, k; cin >> n >> k; vector<pair<ll, ll>> a1, a2; for(int i = 0; i < n/2; ++i){ll x, y; cin >> x >> y; a1.push_back({x,y});} for(int i = n/2; i < n; ++i){ll x, y; cin >> x >> y; a2.push_back({x,y});} int sz1 = a1.size(), sz2 = a2.size(); vector<pair<ll, ll>> smth; for(int i = 0; i < (1<<sz1); ++i){ ll last = 0, x = 0; bool valid = 1; for(int j = 0; j < sz1; ++j){ if(!(i&(1<<j))) continue; if(a1[j].ff >= last){ last = a1[j].ff; x += a1[j].ss; } else { valid = 0; break; } } if(valid) smth.push_back({last, x}); } map<ll, vector<ll>> bar; for(int i = 0; i < (1<<sz2); ++i){ ll fi = inf, last = 0, x = 0, valid = 1; for(int j = 0; j < sz2; ++j){ if(!(i&(1<<j))) continue; if(fi == inf) fi = a2[j].ff; if(a2[j].ff >= last){ last = a2[j].ff; x += a2[j].ss; } else { valid = 0; break; } } if(valid) bar[fi].push_back(x); } ll ans = 0; for(auto i: bar) sort(i.ss.begin(), i.ss.end()); for(auto i: smth){ for(auto u: bar){ if(u.ff >= i.ff){ ll z = lower_bound(u.ss.begin(), u.ss.end(), max(k-i.ss, 0ll))-u.ss.begin(); ans += u.ss.size()-z; } } } 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...