oj.uz

Submission #144745

# Submission time Handle Problem Language Result Execution time Memory
144745 2019-08-17T15:44:58 Z Linca_Robert San (COCI17_san) C++14
0 / 120
 1000 ms 9184 KB 
#include<bits/stdc++.h>
using namespace std;

int N;
long long K, Ans;
pair<int,int> arr[50];
queue< pair<long long,int> > q;
vector<long long> F[2][50];
vector<int> Norm;

inline int msb( int x ){
    int ans = 0;
    while( x != 0 ){
        x >>= 1;
        ans++;
    }
    return ans;
}

inline int mub( int x ){
    if( x == 0 )
        return 0;
    for( int i = 0; ; i++ )
        if( ( (x>>i) & 1 ) == 1 )
            return i + 1;
}

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

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

int main(){

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

    sort( Norm.begin(), Norm.end() );
    Norm.resize( distance( Norm.begin(), unique( Norm.begin(), Norm.end() ) ) );

    //rezolv prima jumatate
    q.push( {0, 0} );
    while( !q.empty() ){
        long long s = q.front().first;
        int msk = q.front().second; q.pop();
        int b = msb( msk );
        for( int i = 1 + b; i <= N / 2; i++ ){
            if( arr[b].first <= arr[i].first || b == 0 ){
                F[0][ get_pos( arr[i].first ) ].push_back( s + arr[i].second );
                q.push( { s + arr[i].second, msk + (1<<(i - 1)) } );
            }
        }
    }

    //rezolv a doua jumatate
    for( int i = N / 2 + 1; i <= N; i++ ){
        q.push( { arr[i].second, (1<<(i - N / 2 - 1)) } );
        F[1][ get_pos( arr[i].first ) ].push_back( arr[i].second );
    }
    while( !q.empty() ){
        long long s = q.front().first;
        int msk = q.front().second; q.pop();
        int b = msb( msk ), b1 = mub( msk );
        for( int i = N / 2 + 1 + b; i <= N; i++ ){
            if( arr[N / 2 + b].first <= arr[i].first ){
                F[1][ get_pos( arr[N / 2 + b1].first ) ].push_back( s + arr[i].second );
                q.push( { s + arr[i].second, msk + (1<<(i - N / 2 - 1)) } );
            }
        }
    }

    for( int i = 0; i < Norm.size(); i++ )
        for( int j = 0; j < F[0][i].size(); j++ )
            sort( F[0][i].begin(), F[0][i].end() );

    for( int i = 0; i < Norm.size(); i++ )
        for( int j = 0; j < F[1][i].size(); j++ )
            sort( F[1][i].begin(), F[1][i].end() );

    //numar perechile combinate
    for( int i = 0; i < Norm.size(); i++ ){
        for( int j = 0; j < F[0][i].size(); j++ ){
            for( int k = i; k < Norm.size(); k++ )
                Ans += cnt( 1, k, K - F[0][i][j] );
        }
    }

    //numar perechile interne
    for( int k = 0; k <= 1; k++ )
        for( int i = 0; i < Norm.size(); i++ )
            for( int j = 0; j < F[k][i].size(); j++ )
                if( F[k][i][j] >= K )
                    Ans++;

    cout << Ans << "\n";

    return 0;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0; i < Norm.size(); i++ )
                     ~~^~~~~~~~~~~~~
san.cpp:97:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0; j < F[0][i].size(); j++ )
                         ~~^~~~~~~~~~~~~~~~
san.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0; i < Norm.size(); i++ )
                     ~~^~~~~~~~~~~~~
san.cpp:101:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0; j < F[1][i].size(); j++ )
                         ~~^~~~~~~~~~~~~~~~
san.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0; i < Norm.size(); i++ ){
                     ~~^~~~~~~~~~~~~
san.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0; j < F[0][i].size(); j++ ){
                         ~~^~~~~~~~~~~~~~~~
san.cpp:107:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for( int k = i; k < Norm.size(); k++ )
                             ~~^~~~~~~~~~~~~
san.cpp:114:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i = 0; i < Norm.size(); i++ )
                         ~~^~~~~~~~~~~~~
san.cpp:115:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for( int j = 0; j < F[k][i].size(); j++ )
                             ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 356 KB Output is correct
2 Incorrect 3 ms 504 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 1396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 2404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 9184 KB Time limit exceeded
2 Halted 0 ms 0 KB -