oj.uz

Submission #108167

# Submission time Handle Problem Language Result Execution time Memory
108167 2019-04-27T19:48:53 Z FiloSanza San (COCI17_san) C++14
96 / 120
 147 ms 66560 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;

//O(2^N/2)
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);
}

//O(log(2^N/2) + N)
int cont(const pair<int, int>& value, const vector<pair<int, int>>& right, const vector<vector<int>>& contH){
    int ans = 0;
    int diff = K-value.first;
    auto it = lower_bound(right.begin(), right.end(), diff, comparer());
    if(it == right.end()) return 0;
    int idx = it - right.begin();
    for(int i=value.second; i<contH[idx].size(); i++) ans += contH[idx][i];
    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];

    int sub = 0;
    map<int, int> remap;
    for(auto i : h) remap[i]++;
    for(auto &i : remap) i.second = sub++;
    for(auto &i : h) i = remap[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());

    vector<int> tmp(sub, 0);
    vector<vector<int>> contH(right.size());
    for(int i=right.size()-1; i>=0; i--){
        tmp[right[i].second]++;
        contH[i] = tmp;
    }
    
    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, contH);

    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";
*/
}

Compilation message

san.cpp: In function 'long long int cont(const std::pair<long long int, long long int>&, const std::vector<std::pair<long long int, long long int> >&, const std::vector<std::vector<long long int> >&)':
san.cpp:35:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=value.second; i<contH[idx].size(); i++) ans += contH[idx][i];
                             ~^~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19888 KB Output is correct
2 Correct 6 ms 1840 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 45688 KB Output is correct
2 Correct 11 ms 3584 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -