Submission #1105328

#TimeUsernameProblemLanguageResultExecution timeMemory
1105328proteam23Cloud Computing (CEOI18_clo)C++14
100 / 100
669 ms2356 KiB
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <random>
#include <chrono>
#include <iomanip>
#include <cmath>
#include <bitset>
#define int long long
#define double long double
#define ii pair<int,int>
#define iii pair<int, ii >
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1ll)
#define turnon(x,y) ((x)|(1ll<<y))
#define turnof(x,y) ((x)^(1ll<<y))
#define oo 1e18
#define pb push_back
#define all(x) x.begin(),x.end()
#define con(mask) mask=(mask-1)&mask
#define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())

#define rand_int mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand_ll mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

using namespace std;

const int mod = 1e9 + 7;
const int base = 29;
const int base_down = 1e9 + 7;
const double EPS = 1e-4;

int n, m;
struct nhan {
    int t;
    int c, f, v;
    
    nhan(int _t = 0, int _c = 0, int _f = 0, int _v = 0): t(_t), c(_c), f(_f), v(_v) {}

    bool operator < (const nhan &other) const {
        if(f == other.f) return t < other.t;
        return f > other.f;
    } 
};

vector<nhan>val;

int dp[2][100005];
//so core
//
signed main() {


    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n;

    int sum_core = 0;

    for(int i = 1; i <= n; i++) {
        int c, f, v;
        cin >> c >> f >> v;

        val.pb(nhan(1, c, f, -v));
        sum_core += c;
    }

    cin >> m;

    for(int i = 1; i <= m; i++) {
        int c, f, v;
        cin >> c >> f >> v;

        val.pb(nhan(2, c, f, v));
    }

    sort(all(val));

    memset(dp, -0x3f, sizeof dp);

    dp[1][0] = 0;

    for(int i = 0; i < val.size(); i++) {
        int cur = i % 2;
        int pre = 1 - cur;

        for(int j = 0; j <= sum_core; j++) {
            //ko chon
            dp[cur][j] = dp[pre][j];

            //chon
            if(val[i].t == 1) {
                if(j >= val[i].c) {
                    dp[cur][j] = max(dp[cur][j], dp[pre][j - val[i].c] + val[i].v);
                }
            }
            else {
                if(j + val[i].c <= sum_core) {
                    dp[cur][j] = max(dp[cur][j], dp[pre][j + val[i].c] + val[i].v);
                }
            }
        }


        for(int j = 0; j <= sum_core; j++) {
            dp[pre][j] = -oo;
        }
    }

    int res = 0;
    int cur = (val.size() - 1) % 2;

    for(int i = 0; i <= sum_core; i++) res = max(res, dp[cur][i]);

    cout << res;


    
    
    


}
//      ProTeam
//(¯`·.·´¯) (¯`·.·´¯)
//`·.¸(¯`·.·´¯)¸ .·
//×°× ` ·.¸.·´ ×°×



Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:94:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<nhan>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < val.size(); i++) {
      |                    ~~^~~~~~~~~~~~
#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...