Submission #675049

#TimeUsernameProblemLanguageResultExecution timeMemory
675049Ahmed57San (COCI17_san)C++14
120 / 120
172 ms21124 KiB
#include<bits/stdc++.h> using namespace std; //BIT Fenwick tree int lim ; int bit[41]={0}; void add(int e,int v){ while(e<=lim){ bit[e]+=v; e+=e&-e; } } long long sum(int e){ long long res = 0; while(e>=1){ res+=bit[e]; e -= e&-e; } return res; } //end BIT long long k,n; vector<pair<long long,long long>> arr(42); int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>k; set<long long> s; for(int i = 0;i<n;i++){ long long a,b;cin>>a>>b; s.insert(a); arr[i] = {a,b}; } map<long long,long long> compress; int z =0; for(auto i:s){ compress[i] = ++z; } lim = z; for(int i = 0;i<n;i++){ arr[i].first = compress[arr[i].first]; } arr[40]={0,0}; long long ans = 0; vector<pair<long long,long long>> v,w; int e = n/2; for(long long mask=1;mask<(1<<e);mask++){ long long s=0,p=40; for(long long i=0;i<e;i++){ if((1<<i)&mask){ if(arr[i].first>=arr[p].first){ s+=arr[i].second; } else{ s=-1; break; } p=i; } } if(s>=k)ans++; if(s!=-1)v.push_back({s,arr[p].first}); } sort(v.begin(),v.end()); vector<pair<long long,long long>> cd(42); for(int i = e;i<n;i++){ cd[i-e] = arr[i]; } cd[40] = {0,0}; n-=e; for(long long mask=1;mask<(1<<n);mask++){ long long s=0,p=40,f=-1; for(long long i=0;i<n;i++){ if((1<<i)&mask){ if(cd[i].first>=cd[p].first){ s+=cd[i].second; if(f==-1){ f = cd[i].first; } } else{ s=-1; break; } p=i; } } if(s>=k)ans++; if(s!=-1)w.push_back({s,f}); } sort(w.begin(),w.end()); int d = v.size()-1; for(int i = 0;i<w.size();i++){ while(d>=0&&v[d].first+w[i].first>=k){add(v[d].second,1);d--;} ans+=sum(w[i].second); } cout<<ans; return 0; }

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0;i<w.size();i++){
      |                   ~^~~~~~~~~
#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...