oj.uz

Submission #144764

# Submission time Handle Problem Language Result Execution time Memory
144764 2019-08-17T16:08:12 Z Linca_Robert San (COCI17_san) C++14
120 / 120
 274 ms 2672 KB 
#include<bits/stdc++.h>
using namespace std;

int N, A, B;
long long K, Ans;
pair<int,int>  arr[50];
vector<long long> F[50];

inline int cnt( int k, long long x ){
    int st = 0, dr = F[k].size() - 1;
    while( st <= dr ){
        int mid = ( st + dr ) >> 1;
        if( F[k][mid] < x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return (int)(F[k].size()) - 1 - dr;
}

int main(){

    cin >> N >> K;
    for( int i = 1; i <= N; i++ )
        cin >> arr[i].first >> arr[i].second;

    A = N / 2; B = N - A;

    for( int msk = 1; msk < (1<<A); msk++ ){

        int lst_p = 0; bool ok = true; long long s = 0;
        for( int i = 0; i < A && ok == true; i++ ){
            if( ( (msk>>i) & 1 ) == 0 )
                continue;
            if( arr[lst_p].first > arr[i + 1].first ){
                ok = false; break; }
            lst_p = i + 1;
            s += arr[i + 1].second;
        }

        if( ok == false )
            continue;
        Ans += ( s >= K ) ? 1 : 0;
        F[lst_p].push_back( s );
    }

    for( int i = 1; i <= A; i++ )
        sort( F[i].begin(), F[i].end() );

    /*
    for( int i = 1; i <= A; i++ ){
        for( int j = 0; j < F[i].size(); j++ )
            cout << F[i][j] << " ";
        cout << "\n";
    }*/

    for( int msk = 1; msk < (1<<B); msk++ ){

        int lst_p = 0, fst_p = 0; bool ok = true; long long s = 0;
        for( int i = 0; i < B && ok == true; i++ ){
            if( ( (msk>>i) & 1 ) == 0 )
                continue;
            if( arr[lst_p].first > arr[i + A + 1].first ){
                ok = false; break; }
            lst_p = i + A + 1;
            if( fst_p == 0 )
                fst_p = i + A + 1;
            s += arr[i + A + 1].second;
        }

        if( ok == false )
            continue;
        Ans += ( s >= K ) ? 1 : 0;

        for( int i = 1; i <= A; i++ ){
            if( arr[i].first <= arr[fst_p].first )
                Ans += cnt( i, K - s );
        }
    }

    cout << Ans << "\n";
    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1012 KB Output is correct
2 Correct 21 ms 504 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 2672 KB Output is correct
2 Correct 118 ms 1648 KB Output is correct