Submission #522954

#TimeUsernameProblemLanguageResultExecution timeMemory
522954ali22413836San (COCI17_san)C++14
120 / 120
68 ms27580 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std ; typedef long long ll; typedef long double ld ; const int N=2e7; const ll inf=1e18 ; const ll mod = 1e9 + 7 ; ll mypower(ll x, ll y){ if(y == 0) return 1 ; if(y == 1) return x ; ll ret = mypower(x , y / 2); ret = (ret * ret) % mod; if(y % 2) ret = ( ret * x ) % mod ; return ret ; } int n , a[50] , b[50] ; ll k , ans ; vector < ll > fi , se , v[50] , al ; bool cmp(ll x , ll y){ return a[x] > a[y] ; } bool cmp2(ll x , ll y){ return a[x] < a[y] ; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k ; for(int i = 0 ; i < n ; i++){ cin >> a[i] >> b[i] ; } for(int i = 0; i <= (n - 1) / 2 ; i++){ fi.push_back(i) ; v[i].clear() ; v[i].push_back(b[i]) ; for(int j = 0 ; j < i ; j++){ if(a[j] <= a[i]){ for(auto p : v[j]){ v[i].push_back(p + b[i]) ; } } } sort(v[i].begin() , v[i].end()) ; for(auto p : v[i]){ ans += (p >= k) ; } } for(int i = n - 1; i > (n - 1) / 2 ; i--){ se.push_back(i) ; v[i].clear() ; v[i].push_back(b[i]) ; for(int j = i + 1 ; j < n ; j++){ if(a[j] >= a[i]){ for(auto p : v[j]){ v[i].push_back(p + b[i]) ; } } } sort(v[i].begin() , v[i].end()) ; for(auto p : v[i]){ ans += (p >= k) ; } } sort(fi.begin() , fi.end() , cmp) ; sort(se.begin() , se.end() , cmp2) ; for(int i = 0; i < se.size() ; i++){ while(!fi.empty() && a[fi.back()] <= a[se[i]]){ ll i = 0 , j = 0 ; vector < ll > x = al , x2 = v[fi.back()] ; vector < ll > ret ; while(i < x.size() && j < x2.size()){ if(x[i] == 0) i++ ; if(x2[j] == 0) j++ ; if(x[i] <= x2[j]){ ret.push_back(x[i]) ; i++ ; } else{ ret.push_back(x2[j]) ; j++ ; } } while(i < x.size()){ ret.push_back(x[i]) ; i++ ; } while(j < x2.size()){ ret.push_back(x2[j]) ; j++ ; } fi.pop_back() ; swap(al , ret) ; } for(auto p : v[se[i]]){ ll q = lower_bound(al.begin() , al.end() , k - p) - al.begin() ; ans += (al.size() - q) ; } } cout << ans << endl ; return 0 ; }

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0;  i < se.size() ; i++){
      |                     ~~^~~~~~~~~~~
san.cpp:71:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             while(i < x.size() && j < x2.size()){
      |                   ~~^~~~~~~~~~
san.cpp:71:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             while(i < x.size() && j < x2.size()){
      |                                   ~~^~~~~~~~~~~
san.cpp:85:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             while(i < x.size()){
      |                   ~~^~~~~~~~~~
san.cpp:89:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while(j < x2.size()){
      |                   ~~^~~~~~~~~~~
#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...