Submission #42312

#TimeUsernameProblemLanguageResultExecution timeMemory
42312wzySan (COCI17_san)C++11
120 / 120
336 ms17252 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define eps (int) 1e9 #define pii pair<int,int> #define int long long int h[41],g[41], n , k; vector<int> alt[50]; set<int> t; map<int,int> compress; int cnt = 0; int32_t main(){ cin>>n>>k; vector<pii> v1 , v2; int sz1 = n/2 + 1; int sz2 = n - sz1; for(int i = 0 ; i < sz1 ; i++){ int x ,y; cin>>x>>y; v1.pb(pii(x,y)); t.insert(x); } for(int i = 0 ; i< sz2 ; i++){ int x,y; cin>>x>>y; v2.pb(pii(x,y)); t.insert(x); } for(auto p : t){ compress[p] = cnt++; } int ans = 0; vector<pii> middle1 , middle2; for(int j = 1 ; j < (1<<sz1) ; j++){ int sumj = 0; bool can = true; int current = 0; for(int i = 0 ; i <sz1; i ++){ if(1<<i & j){ if(current <= v1[i].F){ sumj += v1[i].S; current = v1[i].F; } else can = false; } } if(!can) continue; middle1.pb(pii(sumj , current)); if(sumj >= k) ans++; } for(int j = 1 ; j < (1<<sz2);j++){ int sumj = 0; bool can = true; int current = 0; bool jafoifst = false; int ffst = 0; for(int i = 0 ; i < sz2 ; i++){ if(1<<i & j){ if(current <= v2[i].F){ sumj += v2[i].S; current = v2[i].F; if(!jafoifst){ jafoifst ^= 1; ffst = current; } } else can = false; } } if(!can) continue; if(sumj >= k) ans++; alt[compress[ffst]].pb(sumj); } for(int i = 0 ; i < 50;i++) sort(alt[i].begin() , alt[i].end()); for(auto p : middle1){ int j = compress[p.S]; for(int w = j ; w < 50 ; w++){ int l = 0 , r = ((int)alt[w].size()) - 1; int ansj =-1; while(l<=r){ int mid = (l+r)/2; if(p.F + alt[w][mid] >= k){ ansj = mid; r = mid - 1; } else l = mid + 1; } if(ansj != -1) ans += (int ) alt[w].size() - ansj; } } 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...