Submission #433190

#	Time	Username	Problem	Language	Result	Execution time	Memory
433190		blue	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	374 ms	20808 KiB

bobek

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
Split the matches into two groups of size N/2.
For each group, create a sorted list of all possible subset sums.
Use two pointers to compute the total number of combinations.
*/

int main()
{
    int N;
    long long M;
    cin >> N >> M;

    int a = N/2, b = N - N/2;

    vector<long long> A(a), B(b);

    for(int i = 0; i < a; i++) cin >> A[i];
    for(int j = 0; j < b; j++) cin >> B[j];

    vector<long long> A_sum, B_sum;
    long long temp;

    for(int mask = 0; mask < (1 << a); mask++)
    {
        temp = 0;
        for(int i = 0; i < a; i++) if(mask & (1 << i)) temp += A[i];
        A_sum.push_back(temp);
    }
    sort(A_sum.begin(), A_sum.end());


    for(int mask = 0; mask < (1 << b); mask++)
    {
        temp = 0;
        for(int i = 0; i < b; i++) if(mask & (1 << i)) temp += B[i];
        B_sum.push_back(temp);
    }
    sort(B_sum.begin(), B_sum.end());

    long long a_index = 0;
    long long b_index = B_sum.size()-1;

    long long res = 0;


    for(a_index = 0; a_index < A_sum.size(); a_index++)
    {
        while(A_sum[a_index] + B_sum[b_index] > M)
        {
            if(b_index == 0) break;
            else b_index--;
        }
        if(A_sum[a_index] + B_sum[b_index] > M) break;
        // cout << a_index << ' ' << b_index << '\n';

        res += b_index + 1;
    }

    cout << res << '\n';
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:51:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(a_index = 0; a_index < A_sum.size(); a_index++)
      |                      ~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10