oj.uz

Submission #108161

# Submission time Handle Problem Language Result Execution time Memory
108161 2019-04-27T19:15:46 Z FiloSanza San (COCI17_san) C++14
48 / 120
 1000 ms 20992 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct comparer{
    bool operator()(const pair<int, int>& a, const int& b){
        return a.first < b;
    }
    bool operator()(const int& a, const pair<int, int>& b){
        return a < b.first;
    }
};

int n, N, K;
vector<int> v;
vector<int> h;

void jump(int last, int start, int i, int coins, vector<pair<int, int>>& sum){
    if(i == n && start == -1) return;
    if(i == n) return sum.push_back({coins, i == N ? start : last});
    if(start == -1 || last <= h[i]) jump(h[i], start == -1 ? h[i] : start, i+1, coins + v[i], sum);
    jump(last, start, i+1, coins, sum);
}

int cont(const pair<int, int>& value, const vector<pair<int, int>>& right){
    int ans = 0;
    int diff = K-value.first;
    auto it = lower_bound(right.begin(), right.end(), diff, comparer()) - right.begin();
    
    for(; it<(int)right.size(); it++)if(value.second <= right[it].second)
        ans ++;
    return ans;
}

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

    cin >> N >> K;
    v.resize(N);
    h.resize(N);

    for(int i=0; i<N; i++)
        cin >> h[i] >> v[i];

    vector<pair<int, int>> left, right;
    left.reserve(1<<(N/2));
    right.reserve(1<<(N/2));
    n = N/2;
    jump(-1, -1, 0, 0, left);
    n = N;
    jump(-1, -1, N/2, 0, right);

    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    int ans = 0;
    for(auto i : left) if(i.first >= K) ans++;
    for(auto i : right) if(i.first >= K) ans++;
    for(auto i : left) ans += cont(i, right);

    cout << ans;
/*
    cout << "\n\nDEBUG\n";
    for(auto i : left) cout << i.first << " " << i.second << " "; cout << "\n";
    for(auto i : right) cout << i.first << " " << i.second << " "; cout << "\n";
*/
}

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 1920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 3200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 20992 KB Time limit exceeded
2 Halted 0 ms 0 KB -