Submission #37982

#TimeUsernameProblemLanguageResultExecution timeMemory
37982wasylSan (COCI17_san)C++11
120 / 120
293 ms8504 KiB
#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 < n; ++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 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...