This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <iostream>
#include <algorithm>
#define d(...) __VA_ARGS__
#define all(x) (x).begin(), (x).end()
#define eb(...) emplace_back(__VA_ARGS__)
using namespace std;using ll=long long;
template<class t>using V = vector< t >;
ll res;
int n; ll ka;
V< int > tab;
V< int > ilo;
V< V< ll > > arr;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> ka;
tab.resize( n );
ilo.resize( n );
arr.resize( n );
for ( int i = 0; i < n; ++i )
cin >> tab[i] >> ilo[i];
int pol = n / 2;
for ( int i = 1; i < ( 1 << pol ); ++i )
{
bool fl = true;
int currh = 0;
ll sum = 0;
int last = 0;
for ( int k = 0; k < pol; ++k )
if ( ( 1 << k ) & i )
{
last = k;
if ( tab[k] < currh )
{
fl = false; break;
}
currh = tab[k];
sum += ilo[k];
}
if ( fl )
arr[last].eb( sum );
}
int pop = pol;
if ( pol * 2 < n ) ++pol;
for ( int i = 1; i < ( 1 << pol ); ++i )
{
bool fl = true;
int currh = 0;
ll sum = 0;
int first = 41;
for ( int k = 0; k < pol; ++k )
if ( ( 1 << k ) & i )
{
first = min( first, k + pop );
if ( tab[k + pop] < currh )
{
fl = false; break;
}
currh = tab[k + pop];
sum += ilo[k + pop];
}
if ( fl )
arr[first].eb( sum );
}
for ( int i = 0; i < pop; ++i )
sort( all( arr[i] ) );
for ( int i = 0; i < pop; ++i )
for ( int k = pop; k < n; ++k )
{
if ( tab[i] <= tab[k] )
for ( ll c : arr[k] )
res += arr[i].end() - lower_bound( all( arr[i] ), ka - c );
}
// for ( int i = 0; i < n; ++i )
// {
// cout << i << ": ";
// for ( ll k : arr[i] )
// cout << k << ' ';
// cout << '\n';
// }
for ( int i = 0; i < n; ++i )
res += arr[i].end() - lower_bound( all( arr[i] ), ka );
cout << res << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |