Submission #108161

#	Time	Username	Problem	Language	Result	Execution time	Memory
108161		FiloSanza	San (COCI17_san)	C++14	48 / 120	1071 ms	20992 KiB

san

#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 / 24
• Subtask 2: 24 / 24
• Subtask 3: 0 / 24
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24