제출 #1368400

#제출 시각아이디문제언어결과실행 시간메모리
1368400iancunhaCloud Computing (CEOI18_clo)C++20
100 / 100
620 ms3820 KiB
#include <bits/stdc++.h>
#define int int64_t
#define f first
#define s second
#define opt1 ios_base::sync_with_stdio(false)
#define opt2 cin.tie(NULL)
#define optimize opt1; opt2
#define pb push_back
#define endl "\n"
#define sz(v) (int)v.size()
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
typedef pair<ii, ii> i4;
typedef pair<int, i4> i5;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<i3> vi3;
typedef vector<i4> vi4;
const int inf = 0x6f6f6f6f6f6f;
const int MAX = 200005;
const int LOG = 21;
const int mod = 1e9+7;

int dp[MAX], dp2[MAX];

int32_t main () {
    optimize;
    int n;
    cin >> n;
    vi4 V;
    for (int i = 1; i <= n; i++) {
        int c, r, v;
        cin >> c >> r >> v;
        V.pb({{r, 1}, {c, v}});
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int c, r, v;
        cin >> c >> r >> v;
        V.pb({{r, 0}, {c, v}});
    }
    sort(V.begin(), V.end());
    for (int i = 1; i < MAX; i++)
        dp[i] = dp2[i] = -inf;
    dp[0] = 0;
    dp2[0] = -inf;
    int Z = 0;
    for (int i = 1; i <= sz(V); i++) {
        int C = V[i-1].s.f, v = V[i-1].s.s, 
            T = V[i-1].f.s;
        for (int j = 0; j <= 50*(i-1); j++) {
            if (T == 0) {
                dp2[j+C] = max(dp2[j+C], dp[j]+v);
                dp2[j] = max(dp2[j], dp[j]);
            } else {
                dp2[max(Z, j-C)] = 
                    max(dp2[max(Z, j-C)], dp[j]-v);
                dp2[j] = max(dp2[j], dp[j]);
            }
        } 
        for (int j = 0; j <= 50*i; j++) {
            dp[j] = dp2[j];
            dp2[j] = -inf;
        }
    }
    cout << dp[0] << endl;
    return 0;
}
/*

order by Fj

dp(i, j) = caras i, cores clientes j
if (i+1 == cliente) {
    dp(i+1, j) <= dp(i, j)
    dp(i+1, j+C) <= dp(i, j) - V
} else {
    dp(i+1, j) <= dp(i, j)
    dp(i+1, max(0, j-C)) <= dp(i, j) + V
}


*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…