Submission #783971

#	Time	Username	Problem	Language	Result	Execution time	Memory
783971		c2zi6	Cloud Computing (CEOI18_clo)	C++14	0 / 100	419 ms	1896 KiB

clo

#include <bits/stdc++.h>
#define answer int operator()()

using namespace std;
using ll = long long;

int n, m;
vector<int> c, f, v;
vector<int> C, F, V;

struct test1 {
    answer {
        return 0;
    }
};

struct test2 {
    answer {
        return 0;
    }
};

struct test3 {
    answer {
        return 0;
    }
};

struct test4 {
    //f[i] = F[i] = 1
    const int MAXCNT = 2000 * 50 + 30;
    
    answer {
        ll dp1[MAXCNT + 1]; //maximum value
        for (int i = 0; i <= MAXCNT; i++) dp1[i] = -1e18;
        dp1[0] = 0;
        for (int i = 1; i <= m; i++) {
            ll weight = C[i - 1];
            ll value = V[i - 1];
            for (int j = MAXCNT; j >= 0; j--) {
                if (j - weight < 0) break;
                if (dp1[j-weight] != -1e18) dp1[j] = max(dp1[j], dp1[j-weight]+value);
            }
        }
        
        ll dp2[MAXCNT + 1]; //minimum value
        for (int i = 0; i <= MAXCNT; i++) dp2[i] = 1e18;
        dp2[0] = 0;
        for (int i = 1; i <= n; i++) {
            ll weight = c[i - 1];
            ll value = v[i - 1];
            for (int j = MAXCNT; j >= 0; j--) {
                if (j - weight < 0) break;
                if (dp2[j-weight] != 1e18) dp2[j] = min(dp2[j], dp2[j-weight]+value);
            }
        }
        
        for (int i = 1; i <= MAXCNT; i++) dp1[i] = max(dp1[i], dp1[i-1]);
        for (int i = MAXCNT-1; i >= 0; i--) dp2[i] = min(dp2[i], dp2[i+1]);
        
        ll ans = 0;
        for (int cur = 0; cur <= MAXCNT; cur++) {
            if (dp1[cur] == -1e18 || dp2[cur] == 1e18) continue;
            ll profit = dp1[cur] - dp2[cur];
            ans = max(ans, profit);
        }
        return ans;
    }
};

struct test5 {
    answer {
        return 0;
    }
};

void solve() {
    bool t1, t2, t3, t4, t5;
    t1 = t2 = t3 = t4 = false;
    t5 = true;
    
    cin >> n;
    c = f = v = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i] >> f[i] >> v[i];
        if (f[i] != 1) t5 = false;
    }
    cin >> m;
    C = F = V = vector<int>(m);
    for (int i = 0; i < m; i++) {
        cin >> C[i] >> F[i] >> V[i];
        if (F[i] != 1) t5 = false;
    }
    cout << test4{}() << endl;
    return;
    if (t1) cout << test1{}() << endl;
    else if (t2) cout << test2{}() << endl;
    else if (t3) cout << test3{}() << endl;
    else if (t4) cout << test4{}() << endl;
    else if (t5) cout << test5{}() << endl;
    else cout << -1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--) solve();
}

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