oj.uz

Submission #116883

# Submission time Handle Problem Language Result Execution time Memory
116883 2019-06-14T03:25:45 Z minhcool San (COCI17_san) C++17
120 / 120
 876 ms 10888 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
int n, k, h[41], g[41], ans;
vector<int> ans1[21];
vector<int> ans2;

int ind(int x){
    if(ans2[ans2.size() - 1] < x) return ans2.size();
    int l = 0, r = ans2.size() - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        if(ans2[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l;
}

void bt1(int u, int coins, int last){
    if(last == u && coins) ans1[u].push_back(coins);
    if(u == (n / 2)) return;
    bt1(u + 1, coins, last);
    if(h[u + 1] >= h[last]) bt1(u + 1, coins + g[u + 1], u + 1);
}

void bt2(int u, int coins, int mx){
    if(u == n){
        ans2.push_back(coins);
        return;
    }
    bt2(u + 1, coins, mx);
    if(h[u + 1] >= mx) bt2(u + 1, coins + g[u + 1], h[u + 1]);
}

signed main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> h[i] >> g[i];
    bt1(0, 0, 0);
    ans1[0].push_back(0);
    for(int i = 0; i <= n / 2; i++){
        ans2.clear();
        bt2((n / 2), 0, h[i]);
        sort(ans2.begin(), ans2.end());
        //for(int j = 0; j < ans2.size(); j++) cout << ans2[j] << " ";
        //cout << endl;
        for(int j = 0; j < ans1[i].size(); j++){
            //cout << ans1[i][j] << " ";
            ans += ans2.size() - ind(k - ans1[i][j]);
        }
        //cout << endl;
    }
    cout << ans;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < ans1[i].size(); j++){
                        ~~^~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 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 256 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1280 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 3056 KB Output is correct
2 Correct 9 ms 640 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 10888 KB Output is correct
2 Correct 50 ms 1924 KB Output is correct