oj.uz

Submission #522954

# Submission time Handle Problem Language Result Execution time Memory
522954 2022-02-06T14:19:17 Z ali22413836 San (COCI17_san) C++14
120 / 120
 68 ms 27580 KB 
#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

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()){
      |                   ~~^~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2584 KB Output is correct
2 Correct 1 ms 444 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3292 KB Output is correct
2 Correct 3 ms 1716 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 27580 KB Output is correct
2 Correct 11 ms 4984 KB Output is correct