Submission #116883

#	Time	Username	Problem	Language	Result	Execution time	Memory
116883		minhcool	San (COCI17_san)	C++17	120 / 120	876 ms	10888 KiB

san

#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 (stderr)

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