| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 80913 |
2018-10-23T02:21:19 Z |
luckyboy |
San (COCI17_san) |
C++14 |
|
251 ms |
8996 KB |
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 45
#define maxm 500005
#define pii pair <int,int>
#define Task "San"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,m;
long long k,ans;
pair <long long,long long> a[maxn],b[maxn];
vector <long long> c[maxn],rr;
vector <pair <long long,long long> > d;
void Prepare1()
{
FOR(i,0,(1 << n) - 1)
{
bool ok = 1;
long long add = 0,h = 0;
FOR(j,0,n-1)
if ((i >> j) & 1)
{
add += a[j+1].S;
if (a[j+1].F < h)
{
ok = 0;
break;
}
h = a[j+1].F;
}
if (ok)
{
d.pb(mp(add,h));
}
}
}
void Prepare2()
{
FOR(i,0,(1 << m) - 1)
{
bool ok = 1;
long long add = 0,h = 0;
FOR(j,0,m-1)
if ((i >> j) & 1)
{
add += b[j+1].S;
if (b[j+1].F < h)
{
ok = 0;
break;
}
h = b[j+1].F;
}
if (ok)
{
FOR(j,0,m-1)
if ((i >> j) & 1)
{
c[b[j+1].F].pb(add);
break;
}
}
}
}
int main()
{
//freopen(Task".inp", "r",stdin);
//freopen(Task".out", "w",stdout);
read(n);
read(k);
m = n - n / 2;
n >>= 1;
FOR(i,1,n)
{
read(a[i].F);
read(a[i].S);
rr.pb(a[i].F);
}
FOR(i,1,m)
{
read(b[i].F);
read(b[i].S);
rr.pb(b[i].F);
}
sort(rr.begin(),rr.end());
rr.resize(unique(rr.begin(),rr.end()) - rr.begin());
FOR(i,1,n)
{
a[i].F = upper_bound(rr.begin(),rr.end(),a[i].F) - rr.begin();
}
FOR(i,1,m)
{
b[i].F = upper_bound(rr.begin(),rr.end(),b[i].F) - rr.begin();
}
Prepare1();
Prepare2();
FOR(i,1,rr.size()) sort(c[i].begin(),c[i].end());
for (auto v : d)
{
long long cur = v.F,h = v.S;
if (cur >= k) ++ans;
FOR(i,h,rr.size())
{
int temp = c[i].end() - lower_bound(c[i].begin(),c[i].end(),k - cur);
ans += temp;
}
}
//for (int v : c[1]) cout << v << ' ';
write(ans);
return 0;
}
Compilation message
san.cpp: In function 'int main()':
san.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
^
san.cpp:107:5: note: in expansion of macro 'FOR'
FOR(i,1,rr.size()) sort(c[i].begin(),c[i].end());
^~~
san.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
^
san.cpp:112:9: note: in expansion of macro 'FOR'
FOR(i,h,rr.size())
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
456 KB |
Output is correct |
| 2 |
Correct |
2 ms |
496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1556 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
2320 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
251 ms |
8996 KB |
Output is correct |
| 2 |
Correct |
119 ms |
8996 KB |
Output is correct |
