제출 #94461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94461		tpoppo	San (COCI17_san)	C++14	120 / 120	89 ms	7724 KiB

san

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
ll k;
ll g[41];
ll h[41];

ll rs;

vector<ll> lf[41];
vector<ll> rg[41];

void left_cp(){
    for(int i=0;i<n/2;i++){

        if(g[i] >= k) rs++;

        lf[i].push_back(g[i]);
        for(int j = 0;j<i;j++){
            if(h[i] >= h[j]){
                for(auto el : lf[j]){
                    lf[i].push_back(g[i] + el);

                    if(g[i] + el >= k) rs++;

                }
            }
        }
        sort(lf[i].begin(),lf[i].end());
        /*
        cout<<i<<": ";
        for(auto el : lf[i]) cout<<el<<" ";
        cout<<endl;
        */
    }
}


void right_cp(){
    for(int i=n-1;i>=n/2;i--){

        rg[i].push_back(g[i]);
        if(g[i] >= k) rs++;

        for(int j = n-1;j>i;j--){
            if(h[i] <= h[j]){
                for(auto el : rg[j]){
                    rg[i].push_back(g[i] + el);
                    if(g[i] + el >= k) rs++;
                }
            }
        }
        sort(rg[i].begin(),rg[i].end());
        /*
        cout<<i<<": ";
        for(auto el : rg[i]) cout<<el<<" ";
        cout<<endl;
        */
    }
}

ll merge(){

    for(int i=0;i<n/2;i++){
        for(int j=n-1;j>=n/2;j--){
            if(h[i] <= h[j]){
                //cout<<h[i]<<" => "<<h[j]<<endl;
                for(auto el : lf[i]){
                    /*
                    cout<<k - el<<endl;
                    cout<<i<<": ";
                    for(auto el : rg[j]) cout<<el<<" ";
                    cout<<"\n\n";
                    */
                    rs += rg[j].end() - lower_bound(rg[j].begin(),rg[j].end(),k - el);
                }
            }
        }
    }

    return rs;
}




int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>h[i]>>g[i];
    }
    left_cp();
    right_cp();
    cout<<merge();
    return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24