Submission #1064099

#TimeUsernameProblemLanguageResultExecution timeMemory
1064099vjudge1Cloud Computing (CEOI18_clo)C++17
0 / 100
2 ms1884 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);
    /*for(int i = 1; i <= n + m; i++)
    {
        cout << st[i].c << ' ' << st[i].f << ' ' << st[i].v << '\n';
    }*/
    vector<vector<ll>>dp(n + m + 3, vector<ll>(101, -inf));
    dp[0][0] = 0;
    ll ans = 0;
    for(int i = 1; i <= n + m; i++)
    {
        for(int j = 0; j <= 50; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j]);
            if(st[i].c >= 0)
            {
                dp[i][j + st[i].c] = max(dp[i][j + st[i].c], dp[i - 1][j] + st[i].v);
                ans = max(ans, dp[i][j + st[i].c]);
            }
            else{
                if(j + st[i].c >= 0)
                {
                    dp[i][j + st[i].c] = max(dp[i][j + st[i].c], dp[i - 1][j] + st[i].v);
                    ans = max(ans, dp[i][j + st[i].c]);
                }
            }
        }
    }
    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...