Submission #592717

#	Time	Username	Problem	Language	Result	Execution time	Memory
592717		davi_bart	Cloud Computing (CEOI18_clo)	C++17	100 / 100	606 ms	2252 KiB

clo

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define int ll
using namespace std;
struct obj {
    int c, f, p;
    bool type;
};
int N, M;
vector<obj> v;
int memo[2][100010];
int sol(int pos, int cpu) {
    if (cpu < 0) return -1e18;
    if (pos == v.size()) return 0;
    if (v[pos].type)
        return max(sol(pos + 1, cpu), sol(pos + 1, cpu + v[pos].c) - v[pos].p);
    else
        return max(sol(pos + 1, cpu), sol(pos + 1, cpu - v[pos].c) + v[pos].p);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.pb({a, b, c, 1});
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.pb({a, b, c, 0});
    }
    sort(v.begin(), v.end(), [](const obj &a, const obj &b) {
        if (a.f != b.f) return a.f > b.f;
        if (a.type != b.type) return a.type > b.type;
        return a.p < b.p;
    });
    for (int i = 0; i < 100010; i++) memo[1][i] = 0;
    for (int i = v.size() - 1; i >= 0; i--) {
        for (int j = 0; j < 100010; j++) {
            if (v[i].type)
                memo[0][j] = max(memo[1][j], j + v[i].c < 100010 ? memo[1][j + v[i].c] - v[i].p : -1000000000000000);
            else
                memo[0][j] = max(memo[1][j], j - v[i].c >= 0 ? memo[1][j - v[i].c] + v[i].p : -1000000000000000);
        }
        for (int j = 0; j < 100010; j++) {
            memo[1][j] = memo[0][j];
        }
    }

    cout << memo[0][0] << '\n';
}

Compilation message (stderr)

clo.cpp: In function 'long long int sol(long long int, long long int)':
clo.cpp:18:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (pos == v.size()) return 0;
      |         ~~~~^~~~~~~~~~~

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