Submission #631214

#TimeUsernameProblemLanguageResultExecution timeMemory
631214epicci23San (COCI17_san)C++17
120 / 120
65 ms9064 KiB
#include "bits/stdc++.h" using namespace std; #define pb push_back #define ff first #define ss second #define endl "\n" #define MOD 1000000007 #define int long long #define double long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define what_is(x) cerr << #x << " is " << x << endl; const int N=200005; const long long INF = LLONG_MAX; const int INF2=(int)1e18; const int LOG=20; typedef pair<int,int> pii; typedef tuple<int,int,int> tp; typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq; typedef priority_queue<pii> max_pq; typedef long long ll; //sunlari dusun// /* * kodu kisaltcak fonksiyon * cevaba binary search ya da normal bs * segment tree / sparse table * stack * teklik ciftlik * precomputation * EN ONEMLISI OVERKILLEME * edge case dusunr * constraintlere bak * indisleri kontrol et * dp * greedy * sorting * dfs bfs * sieve */ int n,k; pii arr[45]; vector<int> v[45]; bool vis[(1LL<<22)]; int cnt=0; void f(int ind,int mask,int last,int sum) { //cout << ind << " " << mask << " " << last << " " << sum << endl; if(!vis[mask]) { //cout << "a:" << endl; vis[mask]=1; if(sum>=k) cnt++; for(int i=n/2;i<=n;i++) { if(last==0 || arr[last].ff<=arr[i].ff) { if(sum>=k) { cnt+=sz(v[i]); // cout << "cnt: " << cnt << endl; } else { int need=k-sum; int it=lower_bound(all(v[i]),need)-v[i].begin(); cnt+=sz(v[i])-it; // cout << "cnt: " << cnt << endl; } } } } if(ind==n/2) return; if(last==0 || arr[ind].ff>=arr[last].ff) f(ind+1,mask|(1LL<<ind),ind,sum+arr[ind].ss); f(ind+1,mask,last,sum); } void solve() { cin >> n >> k; for(int i=1;i<=n;i++) cin >> arr[i].ff >> arr[i].ss; for(int i=n;i>=n/2;i--) { v[i].pb(arr[i].ss); for(int j=i+1;j<=n;j++) { if(arr[i].ff <= arr[j].ff) { for(int x:v[j]) v[i].pb(x+arr[i].ss); } } sort(all(v[i])); // for(int x:v[i]) cout << x << " "; //cout << endl; } f(1,0,0,0); cout << cnt << endl; } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); int t=1;//cin>> t; while(t--) solve(); 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...