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<bits/stdc++.h>
using namespace std;
int N;
long long K, Ans;
pair<int,int> arr[50];
queue< pair<long long,int> > q;
vector<long long> F[2][50];
vector<int> Norm;
inline int msb( int x ){
int ans = 0;
while( x != 0 ){
x >>= 1;
ans++;
}
return ans;
}
inline int mub( int x ){
if( x == 0 )
return 0;
for( int i = 0; ; i++ )
if( ( (x>>i) & 1 ) == 1 )
return i + 1;
}
inline int cnt( int k, int H, int x ){
if( F[k][H].empty() )
return 0;
int st = 0, dr = F[k][H].size() - 1;
while( st <= dr ){
int mid = ( st + dr ) >> 1;
if( F[k][H][mid] < x )
st = mid + 1;
else
dr = mid - 1;
}
return F[k][H].size() - 1 - dr;
}
inline int get_pos( int x ){
int st = 0, dr = Norm.size() - 1;
while( st <= dr ){
int mid = ( st + dr ) >> 1;
if( Norm[mid] <= x )
st = mid + 1;
else
dr = mid - 1;
}
return dr;
}
int main(){
cin >> N >> K;
for( int i = 1; i <= N; i++ ){
cin >> arr[i].first >> arr[i].second;
Norm.push_back( arr[i].first );
}
sort( Norm.begin(), Norm.end() );
Norm.resize( distance( Norm.begin(), unique( Norm.begin(), Norm.end() ) ) );
//rezolv prima jumatate
q.push( {0, 0} );
while( !q.empty() ){
long long s = q.front().first;
int msk = q.front().second; q.pop();
int b = msb( msk );
for( int i = 1 + b; i <= N / 2; i++ ){
if( arr[b].first <= arr[i].first || b == 0 ){
F[0][ get_pos( arr[i].first ) ].push_back( s + arr[i].second );
q.push( { s + arr[i].second, msk + (1<<(i - 1)) } );
}
}
}
//rezolv a doua jumatate
for( int i = N / 2 + 1; i <= N; i++ ){
q.push( { arr[i].second, (1<<(i - N / 2 - 1)) } );
F[1][ get_pos( arr[i].first ) ].push_back( arr[i].second );
}
while( !q.empty() ){
long long s = q.front().first;
int msk = q.front().second; q.pop();
int b = msb( msk ), b1 = mub( msk );
for( int i = N / 2 + 1 + b; i <= N; i++ ){
if( arr[N / 2 + b].first <= arr[i].first ){
F[1][ get_pos( arr[N / 2 + b1].first ) ].push_back( s + arr[i].second );
q.push( { s + arr[i].second, msk + (1<<(i - N / 2 - 1)) } );
}
}
}
for( int i = 0; i < Norm.size(); i++ )
for( int j = 0; j < F[0][i].size(); j++ )
sort( F[0][i].begin(), F[0][i].end() );
for( int i = 0; i < Norm.size(); i++ )
for( int j = 0; j < F[1][i].size(); j++ )
sort( F[1][i].begin(), F[1][i].end() );
//numar perechile combinate
for( int i = 0; i < Norm.size(); i++ ){
for( int j = 0; j < F[0][i].size(); j++ ){
for( int k = i; k < Norm.size(); k++ )
Ans += cnt( 1, k, K - F[0][i][j] );
}
}
//numar perechile interne
for( int k = 0; k <= 1; k++ )
for( int i = 0; i < Norm.size(); i++ )
for( int j = 0; j < F[k][i].size(); j++ )
if( F[k][i][j] >= K )
Ans++;
cout << Ans << "\n";
return 0;
}
Compilation message (stderr)
san.cpp: In function 'int main()':
san.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < Norm.size(); i++ )
~~^~~~~~~~~~~~~
san.cpp:97:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int j = 0; j < F[0][i].size(); j++ )
~~^~~~~~~~~~~~~~~~
san.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < Norm.size(); i++ )
~~^~~~~~~~~~~~~
san.cpp:101:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int j = 0; j < F[1][i].size(); j++ )
~~^~~~~~~~~~~~~~~~
san.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < Norm.size(); i++ ){
~~^~~~~~~~~~~~~
san.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int j = 0; j < F[0][i].size(); j++ ){
~~^~~~~~~~~~~~~~~~
san.cpp:107:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int k = i; k < Norm.size(); k++ )
~~^~~~~~~~~~~~~
san.cpp:114:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < Norm.size(); i++ )
~~^~~~~~~~~~~~~
san.cpp:115:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int j = 0; j < F[k][i].size(); j++ )
~~^~~~~~~~~~~~~~~~
# | 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... |