| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 146808 |
2019-08-26T08:52:28 Z |
algorithm16 |
San (COCI17_san) |
C++14 |
|
3 ms |
504 KB |
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include <assert.h>
using namespace std;
typedef long long int llint;
llint n,k,sol;
pair <llint,llint> p[45];
vector <llint> m[25];
vector <llint> v;
vector <llint> v2;
void rek(llint ind,llint x,llint poc,llint a) {
if(ind>=n/2) return;
if(a==1) m[lower_bound(v.begin(),v.end(),p[ind].first)-v.begin()].push_back(x);
else 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,a);
else if(p[i].first>=p[ind].first) rek(i,x+p[i].second,poc,a);
}
}
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[i].size()-(lower_bound(m[i].begin(),m[i].end(),k-x)-m[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()
{
assert(0);
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,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());
rek(-1,0,0,1);
for(llint i=0;i<v.size();i++) {
v2.push_back(v[i]);
//cout << v[i] << endl;
for(llint j=0;j<m[i].size();j++) {
//cout << m[v[i]][j] << " ";
if(m[i][j]>=k) sol+=1;
}
//cout << endl;
}
rek2(n/2-1,0,0);
cout << sol;
return 0;
}
Compilation message
san.cpp: In function 'int main()':
san.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llint i=0;i<v.size();i++) {
~^~~~~~~~~
san.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llint i=0;i<v.size();i++) {
~^~~~~~~~~
san.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llint j=0;j<m[i].size();j++) {
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
