oj.uz

Submission #94461

# Submission time Handle Problem Language Result Execution time Memory
94461 2019-01-18T22:16:44 Z tpoppo San (COCI17_san) C++14
120 / 120
 89 ms 7724 KB 
#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.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1272 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2040 KB Output is correct
2 Correct 5 ms 632 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7724 KB Output is correct
2 Correct 17 ms 1796 KB Output is correct