oj.uz

답안 #1008815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008815 2024-06-26T20:05:00 Z rhavyyz Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 288 ms 20912 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 #3
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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