oj.uz

Submission #572622

# Submission time Handle Problem Language Result Execution time Memory
572622 2022-06-04T21:05:09 Z vladislav11 Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 333 ms 21032 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
ll m;
vector<ll> a;

void f ( vector<ll> &x, vector<ll> &v )
{
    int m = x.size();

    for ( int i=0; i < (1<<m); i++ )
    {
        ll sum = 0;

        for ( int j=0; j<m; j++ )
        if ( (i>>j) & 1 )
            sum += x[j];

        v.push_back( sum );
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    a.resize(n);

    for ( auto& el : a )
        cin >> el;

    vector<ll> x, y;

    {
        int m = n/2;

        for ( int i=0; i<m; i++ )
            x.push_back( a[i] );

        for ( int i=m; i<n; i++ )
            y.push_back( a[i] );
    }

    vector<ll> p, q;

    f( x, p );
    f( y, q );

    sort( p.begin(), p.end() );
    sort( q.begin(), q.end() );

    ll ans = 0;

    for ( auto& el : q )
    {
        ll w = m - el;

        int l = -1, r = int(p.size())-1;

        while ( l < r )
        {
            int mid = ( l + r + 1 ) / 2;

            if ( p[mid] <= w )
                l = mid;
            else
                r = mid-1;
        }

        ans += l+1;
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1992 KB Output is correct
2 Correct 78 ms 5400 KB Output is correct
3 Correct 333 ms 20732 KB Output is correct
4 Correct 80 ms 5452 KB Output is correct
5 Correct 14 ms 1620 KB Output is correct
6 Correct 8 ms 984 KB Output is correct
7 Correct 17 ms 1620 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2896 KB Output is correct
2 Correct 28 ms 2008 KB Output is correct
3 Correct 129 ms 10500 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 984 KB Output is correct
6 Correct 16 ms 1620 KB Output is correct
7 Correct 18 ms 1620 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3540 KB Output is correct
2 Correct 120 ms 6516 KB Output is correct
3 Correct 120 ms 6588 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 79 ms 6600 KB Output is correct
6 Correct 264 ms 20816 KB Output is correct
7 Correct 118 ms 6616 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 12760 KB Output is correct
2 Correct 28 ms 2008 KB Output is correct
3 Correct 9 ms 984 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 6 ms 984 KB Output is correct
6 Correct 228 ms 12704 KB Output is correct
7 Correct 17 ms 1620 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2008 KB Output is correct
2 Correct 79 ms 5472 KB Output is correct
3 Correct 9 ms 976 KB Output is correct
4 Correct 9 ms 984 KB Output is correct
5 Correct 85 ms 6600 KB Output is correct
6 Correct 25 ms 2008 KB Output is correct
7 Correct 314 ms 20732 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 21032 KB Output is correct
2 Correct 29 ms 1904 KB Output is correct
3 Correct 9 ms 984 KB Output is correct
4 Correct 333 ms 20772 KB Output is correct
5 Correct 114 ms 10692 KB Output is correct
6 Correct 17 ms 1620 KB Output is correct
7 Correct 37 ms 2880 KB Output is correct