Submission #144764

#	Time	Username	Problem	Language	Result	Execution time	Memory
144764		Linca_Robert	San (COCI17_san)	C++14	120 / 120	274 ms	2672 KiB

san

#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 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24