제출 #1193933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193933		anmattroi	Cloud Computing (CEOI18_clo)	C++17	100 / 100	352 ms	1348 KiB

clo

#include <bits/stdc++.h>

#define maxn 2001

using namespace std;

int n, m;
struct node {
    int c, f, v, type;
    node() {}
    node(int _c, int _f, int _v, int _type) : c(_c), f(_f), v(_v), type(_type) {}

    bool operator < (const node &t) const {
        if (f != t.f) return f < t.f;
        if (type != t.type) return type < t.type;
        if (v != t.v) return v < t.v;
        return c < t.c;
    }
};
node a[maxn], b[maxn];
node c[maxn+maxn];
int id = 0;
int64_t f[100001];

inline void cmax(int64_t &x, int64_t y) {if (x < y) x = y;}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].c >> a[i].f >> a[i].v;
        c[++id] = node(a[i].c, a[i].f, a[i].v, 1);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> b[i].c >> b[i].f >> b[i].v;
        c[++id] = node(b[i].c, b[i].f, b[i].v, -1);
    }

    sort(c + 1, c + id + 1);
    for (int i = 1; i <= 100000; i++) f[i] = LLONG_MIN/2;
    for (int o = id; o >= 1; o--) {
        int x = c[o].c, val = -1 * c[o].v * c[o].type;
        int64_t ds = LLONG_MIN/2;
        if (c[o].type == -1) {
            int lim = 100000-x;
            for (int i = 0; i <= lim; i++) cmax(f[i], f[i+x]+val);
        } else {
            int lim = x;
            for (int i = 100000; i >= x; i--) cmax(f[i], f[i-x]+val);
        }
    }
    int64_t ds = 0;
    for (int i = 0; i <= 100000; i++) cmax(ds, f[i]);
    cout << ds;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10