Submission #1008815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1008815	2024-06-26T20:05:00 Z	rhavyyz	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	288 ms	20912 KB

bobek

#include "bits/stdc++.h"
// #include<bit>
// #define err(x) cerr << "["#x"]  " << (x) << "\n"
// #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
// #define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
// #define all(a) a.begin(), a.end()
// #define pb push_back
// typedef long long ll;
// typedef long double ld;
// const int MOD = 1000000007;
// mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());

#define int long long
using namespace std;

vector<int> vals;


int begin_bb(int v)
{
    int l = 0, r = vals.size()-1;

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

        if(vals[middle] >= v)
            r = middle -1;
        else
            l = middle + 1;
    }

    return l;
}

int end_bb(int v)
{
    int l = 0, r = vals.size()-1;

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

        if(vals[middle] > v)
            r = middle -1;
        else
            l = middle + 1;
    }

    return l;
}

int solve() 
{
    int n, T;

    cin >> n >> T;

    vector<int>  v1;

    int tot = 0;
    for(int i = 0; i < n/2; i++)
    {
        int number; cin >> number;
        // cout << number << ' ';
        int curr_size = vals.size();

        for(int i = 0; i < curr_size; i++)
        {
            vals.push_back(vals[i] + number);
            if(vals[i] + number <= T)
                tot++;
        }
        if(number <= T)
            tot++;
        vals.push_back(number);
    }

    // cout << tot << endl;

    // cout << "| ";

    // for(auto a : vals)
    //     cout << a << ' ';
    // cout << endl;

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

    // cout << begin_bb(1800) << ' ' << end_bb(1800) << endl;

    for(int i = n/2; i < n; i++)
    {
        int number; cin >> number;
        // cout << number <<' ';
        int curr_size = v1.size();

        for(int i = 0; i < curr_size; i++)
        {    
            v1.push_back(v1[i] + number);

            if(v1[i] + number <= T)
                tot++;
            int end_ = end_bb(T-(v1[i] + number));
            // int begin_ = begin_bb(T-(v1[i] + number));

            // if(begin_ == end_)
            //     continue;

            tot += end_;

        }
        v1.push_back(number);
        if(number <= T)
            tot++;
        int end_ = end_bb(T-number);
        // int begin_ = begin_bb(T-number);
        // cout << number << ' ' << T << endl;
        // cout << end_ << endl;
        // cout << begin_ << endl;
        // if(begin_ == end_)
        //     continue;   
        tot += end_;
    }

    // cout << endl;
    cout << tot + 1 << endl;

    return 1;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    
    // cin >> t;
    while (t--)
        solve();

    // priority_queue<int> q;

    // q.push(3);
    // q.push(2);
    // q.push(1);


}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2096 KB	Output is correct
2	Correct	58 ms	5572 KB	Output is correct
3	Correct	279 ms	20836 KB	Output is correct
4	Correct	67 ms	5456 KB	Output is correct
5	Correct	5 ms	1752 KB	Output is correct
6	Correct	3 ms	1116 KB	Output is correct
7	Correct	6 ms	1756 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2908 KB	Output is correct
2	Correct	18 ms	2140 KB	Output is correct
3	Correct	107 ms	10588 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	3 ms	1116 KB	Output is correct
6	Correct	6 ms	1632 KB	Output is correct
7	Correct	6 ms	1756 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	3660 KB	Output is correct
2	Correct	99 ms	6584 KB	Output is correct
3	Correct	90 ms	6732 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	22 ms	6744 KB	Output is correct
6	Correct	88 ms	20912 KB	Output is correct
7	Correct	29 ms	6644 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	208 ms	12812 KB	Output is correct
2	Correct	15 ms	2144 KB	Output is correct
3	Correct	5 ms	1116 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	2 ms	1088 KB	Output is correct
6	Correct	62 ms	12868 KB	Output is correct
7	Correct	8 ms	1752 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2144 KB	Output is correct
2	Correct	58 ms	5572 KB	Output is correct
3	Correct	4 ms	1112 KB	Output is correct
4	Correct	5 ms	1112 KB	Output is correct
5	Correct	26 ms	6632 KB	Output is correct
6	Correct	7 ms	2144 KB	Output is correct
7	Correct	102 ms	20840 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	20836 KB	Output is correct
2	Correct	19 ms	2140 KB	Output is correct
3	Correct	5 ms	1116 KB	Output is correct
4	Correct	288 ms	20820 KB	Output is correct
5	Correct	41 ms	10688 KB	Output is correct
6	Correct	7 ms	1752 KB	Output is correct
7	Correct	11 ms	2908 KB	Output is correct

Submission #1008815

Compilation message