Submission #681875

#TimeUsernameProblemLanguageResultExecution timeMemory
681875Doncho_BonbonchoSan (COCI17_san)C++14
0 / 120
300 ms54564 KiB
#include <algorithm> #include <bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int MAX_N = 1e6; const int INF = 1e9; const int mod = 1e9 + 7; int n, k; std::vector<ll> L[MAX_N]; std::vector<ll> R[MAX_N]; ll h[MAX_N]; ll c[MAX_N]; std::vector<int> hs; void left( int pos, int currH, int sum ){ if( pos == n/2 ){ int ind = std::lower_bound( hs.begin(), hs.end(), currH ) - hs.begin(); L[ind].push_back(sum); return; } left( pos +1, currH, sum ); if( currH <= h[pos] ){ left( pos +1, h[pos], sum + c[pos] ); } } void right( int pos, int first, int currH, int sum ){ if( pos == n ){ int ind = std::lower_bound( hs.begin(), hs.end(), first ) - hs.begin(); R[ind].push_back( sum ); return ; } right( pos +1, first, currH, sum ); if( h[pos] >= currH ){ if( first == 0 ) first = h[pos]; right( pos +1, first, h[pos], sum + c[pos] ); } } int main () { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin>>n>>k; for( int i=0 ; i<n ; i++ ){ std::cin>>h[i]>>c[i]; hs.push_back( h[i] ); } hs.push_back(0); std::sort( hs.begin(), hs.end() ); left( 0, 0, 0 ); right(n/2, 0, 0, 0); /* std::cerr<<" L:\n"; for( int i=0 ; i<n ; i++ ){ std::cerr<<i<<" : "; for( auto j : L[i] ){ std::cerr<<j<<" "; } std::cerr<<"\n"; } std::cerr<<" R:\n"; for( int i=0 ; i<n ; i++ ){ std::cerr<<i<<" : "; for( auto j : R[i] ){ std::cerr<<j<<" "; } std::cerr<<"\n"; } */ for( int i=0 ; i<(int)hs.size() ; i++ ) std::sort( R[i].begin(), R[i].end() ); ll nas = 0; for( int i=0 ; i<(int)hs.size(); i++ ){ // std::cerr<<i<<":\n"; for( auto it : L[i] ){ nas += R[0].end() - std::lower_bound( R[0].begin(), R[0].end(), k - it ); // std::cerr<<" "<<it<<"\n"; for( int j=i ; j<(int)hs.size() ; j++ ){ ll currNas = R[j].end() - std::lower_bound( R[j].begin(), R[j].end(), k-it ); // std::cerr<<" # "<<j<<" "<<currNas<<"\n"; nas += currNas; } } } std::cout<<nas<<"\n"; return 0; }
#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...