Submission #1289090

#TimeUsernameProblemLanguageResultExecution timeMemory
1289090beheshtCloud Computing (CEOI18_clo)C++20
100 / 100
861 ms3656 KiB
#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e14 + (35 / 10); // 35 ---> 36
const int MAXN = 2e3 + (35 / 10); // 35 ---> 36

arr(3) Q[MAXN * 2];
int dp[2][MAXN * 100];

bool cmp(arr(3) a, arr(3) b){

    if(a[1] != b[1])
        return a[1] > b[1];

    return a[0] > b[0];
}

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
    cin >> n;

    // computer

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++)
            cin >> Q[i][j];

        Q[i][2] *= -1;
    }

    int m;
    cin >> m;

    for(int i = n + 1; i <= n + m; i++){
        for(int j = 0; j < 3; j++)
            cin >> Q[i][j];

        Q[i][0] *= -1;
    }

    sort(Q + 1, Q + n + m + 1, cmp);

    for(int i = 1; i <= (n + m) * 50; i++)
        dp[0][i] = -INF;

    int ans = 0;

    for(int i = 1; i <= n + m; i++){
        auto [c, f, v] = Q[i];
        // d4(i, c, f, v);

        for(int j = 0; j <= (n + m) * 50; j++){

            dp[i & 1][j] = dp[(i - 1) & 1][j];

            if(0 <= j - c && j - c <= (n + m) * 50)
                dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j - c] + v);

            ans = max(ans, dp[i & 1][j]);

            // d1(ans);
            // d3(j, dp[i][j], dp[i][j - c]);
        }
    }

    cout << ans << endl;
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 

*/
#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...