oj.uz

Submission #82911

# Submission time Handle Problem Language Result Execution time Memory
82911 2018-11-02T20:03:30 Z Milki San (COCI17_san) C++14
120 / 120
 190 ms 5792 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 45;

ll n, k, sol;
ll h[MAXN], g[MAXN];
vector <ll> sazmi;
vector <ll> v[MAXN];

int get_id(ll x){
    return lower_bound(sazmi.begin(), sazmi.end(), x) - sazmi.begin();
}

void brut(int lo, int hi){
    REP(i, 1 << (hi - lo + 1)){
        ll sum = 0, last = 0;
        REP(j, hi + 1){
            if(i & (1 << j)){
                if(h[j] >= last){
                    last = h[j];
                    sum += g[j];
                }
                else{
                    last = -1;
                    break;
                }
            }
        }
        if(last != -1)
            v[last].pb(sum);
    }
}

vector <ll> sazetko;

void solve(int x){
    REP(i, x)
        sort(v[h[i]].begin(), v[h[i]].end());

    REP(i, 1 << (n / 2)){

        ll sum = 0, first = 50, last = 0;
        REP(j, n / 2){
            if(i & (1 << j)){
                int idx = j + x;
                if(h[idx] >= last){
                    if(first == 50) first = h[idx];
                    last = h[idx];
                    sum += g[idx];
                }
                else{
                    last = -1;
                    break;
                }
            }
        }
        if(last != -1){
            for(auto it : sazetko){
                if(it <= first){
                    if(sum >= k){
                        sol += sz(v[it]);
                    }
                    else{
                        ll threshold = k - sum;
                        sol += sz(v[it]) - (lower_bound(v[it].begin(), v[it].end(), threshold) - v[it].begin());
                    }
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> k;
    REP(i, n){
        cin >> h[i] >> g[i];
        sazmi.pb(h[i]);
    }
    sort(sazmi.begin(), sazmi.end());
    sazmi.erase(unique(sazmi.begin(), sazmi.end()), sazmi.end());
    REP(i, n){
        h[i] = get_id(h[i]) + 1;
        if(i <= (n - 1) / 2) sazetko.pb(h[i]);
    }
    sazetko.pb(0);
    sort(sazetko.begin(), sazetko.end());
    sazetko.erase(unique(sazetko.begin(), sazetko.end()), sazetko.end());

    int mid = (n - 1) / 2;
    brut(0, mid);
    solve(mid + 1);
    cout << sol;
}

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 500 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1144 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1252 KB Output is correct
2 Correct 28 ms 1252 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 5792 KB Output is correct
2 Correct 121 ms 5792 KB Output is correct