Submission #167841

#	Time	Username	Problem	Language	Result	Execution time	Memory
167841		pavel_guskov	Cloud Computing (CEOI18_clo)	C++14	100 / 100	2295 ms	2168 KiB

clo

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")

using namespace std;

const int MAXN = 2005;
const int MAXCOL = 101;
const long long INF = 1e18;

typedef long long ll;

int n, m;
vector<pair<int, pair<int, int>>> comp;
vector<pair<int, pair<int, int>>> cust;
ll dp[MAXCOL][MAXN];
int ind = 0;

void get_index(int f) {
    while(ind < n && comp[ind].first >= f) ++ind;
}

void fill() {
    for (int i = 0; i < MAXCOL; ++i) for (int j = 0; j < MAXN; j++) dp[i][j] = -INF;
}

void outdp() {
    for (int i = 0; i <= n; i++) {
        for (int col = 0; col <= 30; ++col) {
            cout << "i: " << i << ' ' << col << ' ' << dp[i][col] << endl;
        }
    }
}

void solve() {
    fill();
    for (int j = 0; j < n; j++) dp[0][j] = 0;
    for (int i = 0; i < m; i++) {
        int curf = cust[i].first, curc = cust[i].second.first, curv = cust[i].second.second;
        get_index(curf);
        for (int j = 0; j <= n; j++) {
            for (int col = 0; col < MAXCOL; ++col) {
                if (dp[col][j] == -INF) continue;
                if (j < ind) {
                    if (col + comp[j].second.first < MAXCOL) {
                        dp[col + comp[j].second.first][j + 1] = max(dp[col + comp[j].second.first][j + 1],
                                        dp[col][j] - comp[j].second.second);
                    }
                }
                if (j != n) dp[col][j + 1] = max(dp[col][j + 1], dp[col][j]);
                if (curc <= col) {
                    dp[col - curc][j] = max(dp[col - curc][j],
                    dp[col][j] + curv);
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < MAXCOL; j++) {
            ans = max(ans, dp[j][i]);
        }
    }
    cout << ans << endl;
}

void outvector(vector<pair<int, pair<int, int>>>& a) {
    int sz = a.size();
    for (int i = 0; i < sz; ++i) {
        cout << "i: " << i << endl;
        cout << a[i].first << ' ' << a[i].second.first << ' ' << a[i].second.second << endl;
    }
}

int main() {
    //freopen("test.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    comp.resize(n);
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        comp[i] = {f, {c, v}};
    }
    cin >> m;
    cust.resize(m);
    for (int i = 0; i < m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        cust[i] = {f, {c, v}};
    }
    sort(comp.begin(), comp.end());
    reverse(comp.begin(), comp.end());
    sort(cust.begin(), cust.end());
    reverse(cust.begin(), cust.end());
   //cout << "comp: " << endl;
   //// outvector(comp);
   // cout << "cust: " << endl;
    //outvector(cust);
    solve();
    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