Submission #81042

#TimeUsernameProblemLanguageResultExecution timeMemory
81042ngot23San (COCI17_san)C++11
120 / 120
298 ms3120 KiB
#include<bits/stdc++.h> #define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i) #define Task "" using namespace std; const int N=45; vector <long long > v[25]; int n, b[25], cnt; long long k, ans=0, h[N], g[N]; int get(int xx, int i) { return (xx>>i)&1; } //#define TEST int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef TEST freopen(".inp", "w", stdout); srand(time(NULL)); int xx=rand()%15+1; cout << xx << ' ' << rand()%15+1 << '\n'; rep(i, 1, xx) { cout << rand()%10+1 << ' '; cout << rand()%10+1 << '\n'; } #else //freopen(Task".inp", "r", stdin); //freopen(Task".out", "w", stdout); cin >> n >> k; rep(i, 1, n) cin >> h[i] >> g[i]; int num=n>>1; rep(i, 1, (1ll<<num)-1) { cnt=0; rep(j, 1, num) { if(get(i, j-1)) b[++cnt]=j; } bool ok=0; rep(j, 2, cnt) { if(h[b[j]]<h[b[j-1]]) { ok=1; break; } } if(ok) continue; long long xx=0; rep(j, 1, cnt) { xx+=g[b[j]]; } v[b[cnt]].push_back(xx); if(xx>=k) ++ans; } rep(i, 1, num) sort(v[i].begin(), v[i].end()); int num2=n-num; rep(i, 1, (1ll<<num2)-1) { cnt=0; rep(j, 1, num2) { if(get(i, j-1)) b[++cnt]=j+num; } bool ok=0; rep(j, 2, cnt) { if(h[b[j]]<h[b[j-1]]) { ok=1; break; } } if(ok) continue; long long xx=0; rep(j, 1, cnt) xx+=g[b[j]]; if(xx>=k) ++ans; rep(j, 1, num) { if((h[j]>h[b[1]])||(v[j].back()<(long long)k-xx)) continue; int id=lower_bound(v[j].begin(), v[j].end(), (long long)k-xx)-v[j].begin(); ans+=v[j].size()-id; } } cout << ans; #endif // TEST 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...