oj.uz

Submission #1110883

# Submission time Handle Problem Language Result Execution time Memory
1110883 2024-11-10T18:37:38 Z eyadooz Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 463 ms 10840 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <math.h>
#include <array>
#include <random>
#include <bitset>
#include <climits>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define endl '\n'
#define mod 1000000007
#define INF 0x3f3f3f3f
#define int long long

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")
#pragma GCC target("popcnt")

template <class x>
using ordered_set = tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>;

typedef pair<int, int> ipair;

signed main()
{
    cin.tie(0)->sync_with_stdio(0);

    long long a, b;

    cin >> a >> b;

    vector<int> p1, p2;
    for (int i = 0; i < a; i++)
    {
        if (i < ((a + 1) / 2))
        {
            int x;

            cin >> x;

            p1.push_back(x);
        }
        else
        {
            int x;

            cin >> x;

            p2.push_back(x);
        }
    }

    vector<long long> asd;
    for (int i = 0; i < (1 << p2.size()); i++)
    {
        long long sum = 0;
        for (int j = 0; j < p2.size(); j++)
        {
            if (i & (1 << j))
            {
                sum += p2[j];
            }
        }

        asd.push_back(sum);
    }

    sort(asd.begin(), asd.end());

    long long ans = 0, sum = 0;
    for (int i = 0; i < (1 << p1.size()); i++)
    {
        long long sum = 0;
        for (int j = 0; j < p1.size(); j++)
        {
            if (i & (1 << j))
                sum += p1[j];
        }

        ans += upper_bound(asd.begin(), asd.end(), (b - sum)) - asd.begin();
    }

    cout << ans;
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:71:27: 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]
   71 |         for (int j = 0; j < p2.size(); j++)
      |                         ~~^~~~~~~~~~~
bobek.cpp:88:27: 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]
   88 |         for (int j = 0; j < p1.size(); j++)
      |                         ~~^~~~~~~~~~~
bobek.cpp:84:24: warning: unused variable 'sum' [-Wunused-variable]
   84 |     long long ans = 0, sum = 0;
      |                        ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 980 KB Output is correct
2 Correct 98 ms 3532 KB Output is correct
3 Correct 441 ms 10828 KB Output is correct
4 Correct 93 ms 3532 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct
6 Correct 8 ms 756 KB Output is correct
7 Correct 17 ms 980 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1488 KB Output is correct
2 Correct 32 ms 980 KB Output is correct
3 Correct 179 ms 6600 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 16 ms 980 KB Output is correct
7 Correct 15 ms 980 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1508 KB Output is correct
2 Correct 145 ms 3704 KB Output is correct
3 Correct 148 ms 3532 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 82 ms 3600 KB Output is correct
6 Correct 241 ms 10660 KB Output is correct
7 Correct 81 ms 3532 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 6600 KB Output is correct
2 Correct 28 ms 980 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 179 ms 6752 KB Output is correct
7 Correct 15 ms 980 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 980 KB Output is correct
2 Correct 88 ms 3704 KB Output is correct
3 Correct 9 ms 724 KB Output is correct
4 Correct 11 ms 980 KB Output is correct
5 Correct 100 ms 3532 KB Output is correct
6 Correct 24 ms 980 KB Output is correct
7 Correct 243 ms 10692 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 10832 KB Output is correct
2 Correct 31 ms 980 KB Output is correct
3 Correct 10 ms 724 KB Output is correct
4 Correct 463 ms 10840 KB Output is correct
5 Correct 120 ms 6600 KB Output is correct
6 Correct 16 ms 980 KB Output is correct
7 Correct 30 ms 1488 KB Output is correct