MINROAD - VOI 2014 - Con đường Tùng Trúc

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;

const int INF = (int) 1e9 + 7;

int main() {
    int n, a, b; scanf("%d %d %d", &n, &a, &b);
    vector<pair<int, int> > tree (n);
    for(int i = 0; i < n; ++i) {
        scanf("%d %d", &tree[i].first, &tree[i].second);
    }
    sort(tree.begin(), tree.end());
    vector<int> pos1 (n), pos2 (n);
    int x = 0, y = 0, res = INF;
    for(int i = 0; i < n; ++i) {
        if(tree[i].second == 1) {
            pos1[x++] = tree[i].first;
        } else {
            pos2[y++] = tree[i].first;
        }
        if(x >= a && y >= b) {
            res = min(res, tree[i].first - min(pos1[x - a], pos2[y - b]));
        }
    }
    printf("%d\n", res == INF ? -1 : res);
    return 0;
}

Download