记录编号	389079	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Oct05]奶牛航班	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2017-03-30 16:30:54	内存使用	0.54 MiB

//KZNS
#include <cstdio>
#include <vector>
#include <utility>
#include <set>
#include <algorithm>
using namespace std;
#define Nmax 10010
int K, N, C;
vector<pair<int, int> > upls[Nmax];
vector<pair<int, int> > dols[Nmax];
void init() {
    scanf("%d %d %d", &K, &N, &C);
    int S, E, M;
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d", &S, &E, &M);
        if (S < E)
            upls[S].push_back(make_pair(E, M));
        else
            dols[S].push_back(make_pair(E, M));
    }
}
int ans = 0;
int cnt = 0;
void workup() {
    multiset<int> st;
    multiset<int>::iterator it;
    for (int i = 1; i <= N; i++) {
        while (cnt) {
            it = st.begin();
            if ((*it) <= i) {
                st.erase(it);
                cnt--;
                ans++;
            }
            else
                break;
        }
        sort(upls[i].begin(), upls[i].end());
        int a, b;
        for (int j = 0; j < (int)upls[i].size(); j++) {
            a = upls[i][j].first;
            b = upls[i][j].second;
            while (b) {
                if (cnt < C) {
                    st.insert(a);
                    cnt++;
                    b--;
                }
                else {
                    it = st.end();
                    it--;
                    if ((*it) > a) {
                        st.erase(it);
                        st.insert(a);
                        b--;
                    }
                    else {
                        goto fn;
                    }
                }
            }
        }
        fn:;
    }
}
void workdo() {
    cnt = 0;
    multiset<int> st;
    multiset<int>::iterator it;
    for (int i = N; i >= 1; i--) {
        while (cnt) {
            it = st.end();
            it--;
            if ((*it) >= i) {
                st.erase(it);
                cnt--;
                ans++;
            }
            else
                break;
        }
        sort(dols[i].begin(), dols[i].end());
        int a, b;
        for (int j = dols[i].size()-1; j >= 0; j--) {
            a = dols[i][j].first;
            b = dols[i][j].second;
            while (b) {
                if (cnt < C) {
                    st.insert(a);
                    cnt++;
                    b--;
                }
                else {
                    it = st.begin();
                    if ((*it) < a) {
                        st.erase(it);
                        st.insert(a);
                        b--;
                    }
                    else {
                        goto fn;
                    }
                }
            }
        }
        fn:;
    }
}
int main() {
    freopen("cowflight.in", "r", stdin);
    freopen("cowflight.out", "w", stdout);
    init();
    workup();
    workdo();
    printf("%d\n", ans);
    return 0;
}
//UBWH