Submission #146805

#TimeUsernameProblemLanguageResultExecution timeMemory
146805algorithm16San (COCI17_san)C++14
0 / 120
1072 ms7524 KiB
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<map> #include<set> using namespace std; typedef long long int llint; llint dp[45],n,k,sol; pair <llint,llint> p[45]; map <llint,vector <llint> > m; vector <llint> v; void rek(llint ind,llint x,llint poc) { if(ind>=n/2) return; m[p[ind].first].push_back(x); v.push_back(p[ind].first); llint c=n/2; for(llint i=ind+1;i<c;i++) { if(ind==-1) rek(i,x+p[i].second,p[i].first); else if(p[i].first>=p[ind].first) rek(i,x+p[i].second,poc); } } void rek2(llint ind,llint x,llint poc) { //cout << ind << " " << x << " " << poc << endl; if(ind>=n) return; if(ind>=n/2) { //cout << ind << " " << x << " " << poc << endl; llint ind1=lower_bound(v.begin(),v.end(),poc+1)-v.begin(); //if(p[ind1].first==poc) ind1+=1; for(llint i=0;i<ind1;i++) { sol+=m[v[i]].size()-(lower_bound(m[v[i]].begin(),m[v[i]].end(),k-x)-m[v[i]].begin()); //cout << v[i] << " " << sol << endl; } } for(llint i=ind+1;i<n;i++) { //cout << i << " " << p[i].first << endl; if(ind==n/2-1) rek2(i,x+p[i].second,p[i].first); else if(p[i].first>=p[ind].first) rek2(i,x+p[i].second,poc); } } int main() { cin >> n >> k; for(llint i=0;i<n;i++) { cin >> p[i].first >> p[i].second; if(p[i].second>=k) sol+=1; } rek(-1,0,0); sort(v.begin(),v.end()); for(llint i=0;i<v.size();i++) { sort(m[v[i]].begin(),m[v[i]].end()); } v.erase(unique(v.begin(),v.end()),v.end()); for(llint i=0;i<v.size();i++) { //cout << v[i] << endl; for(llint j=0;j<m[v[i]].size();j++) { //cout << m[v[i]][j] << " "; if(m[v[i]][j]>=k) sol+=1; } //cout << endl; } rek2(n/2-1,0,0); cout << sol; return 0; }

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llint i=0;i<v.size();i++) {
                ~^~~~~~~~~
san.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llint i=0;i<v.size();i++) {
                ~^~~~~~~~~
san.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llint j=0;j<m[v[i]].size();j++) {
                 ~^~~~~~~~~~~~~~~
#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...