Submission #1064453

#TimeUsernameProblemLanguageResultExecution timeMemory
1064453vjudge1Cloud Computing (CEOI18_clo)C++17
18 / 100
36 ms59996 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 2003;
const ll inf = 1e18;
int n, m;
struct Edge{
    int c;
    ll f, v;
};

Edge st[2 * maxn + 7];

bool cmp(Edge a, Edge b)
{
    if(a.f == b.f) return a.c > b.c;
    return a.f > b.f;
}

int main()
{
   // freopen("CLOUDCOMPUTING.INP", "r", stdin);
   // freopen("CLOUDCOMPUTING.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int c;
        ll f, v;
        cin >> c >> f >> v;
        st[i].c = c;
        st[i].f = f;
        st[i].v = -v;
    }
    cin >> m;
    for(int i = 1 + n; i <= n + m; i++)
    {
        int c;
        ll f, v;
        cin >> c >> f >> v;
        st[i].c = -c;
        st[i].f = f;
        st[i].v = v;
    }
    sort(st + 1, st + n + m + 1, cmp);
    vector<vector<ll>>dp(n + m + 8, vector<ll>(maxn + 3, -inf));
    ll ans = -inf;
    for(int i = 0; i <= n + m; i++)
    {
        dp[i][0] = 0;
       // cout << st[i].c << ' ' << st[i].f << ' ' << st[i].v << '\n';
    }
    for(int i = 1; i <= n + m; i++)
    {
        for(int j = 500; j >= 0; j--)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= st[i].c && dp[i - 1][j - st[i].c] != -inf)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - st[i].c] + st[i].v);
                ans = max(ans, dp[i][j]);
            }
        }
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...