Submission #142882

#TimeUsernameProblemLanguageResultExecution timeMemory
142882OrtSan (COCI17_san)C++11
48 / 120
1067 ms376 KiB
#include<bits/stdc++.h> #define ALL(c) (c).begin(),(c).end() #define ll long long #define pb push_back #define sz(a) ((int)(a.size())) #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define N 25 using namespace std; typedef pair<ll,ll> pll; int n, fh, sh; ll k, hi, gi, sol, curr, sum, lstc; ll h[N], g[N]; vector<ll> t[N]; bool flag; int main() { IO; cin >> n >> k; fh = n>>1; sh = n-fh; for(int i=0;i<n;i++) cin >> h[i] >> g[i]; for(int i=1;i<(1<<fh);i++) { curr = 0; sum = 0; flag = 0; lstc = -1; for(int j=0;j<fh;j++) if((i>>j)&1) { if(h[j]>=curr) curr = h[j], sum += g[j], lstc = j; else {flag = 1; break;} } if(sum>=k && !flag) sol++; if(flag) continue; t[lstc].pb(sum); } for(int i=0;i<fh;i++) sort(ALL(t[i])); for(int i=1;i<(1<<sh);i++) { curr = 0; sum = 0; flag = 0; lstc = -1; for(int j=0;j<sh;j++) if((i>>j)&1) { if(lstc==-1) lstc = h[j+fh]; if(h[j+fh]>=curr) curr = h[j+fh], sum += g[j+fh]; else {flag = 1; break;} } if(sum>=k && !flag) sol++; if(flag) continue; for(int j=0;j<fh;j++) if(h[j]<=lstc) sol += (t[j].end()-lower_bound(ALL(t[j]),k-sum)); } cout << sol; return 0; }
#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...