Submission #1310466

#TimeUsernameProblemLanguageResultExecution timeMemory
1310466hyyhCloud Computing (CEOI18_clo)C++20
54 / 100
221 ms1476 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
using namespace std;
#define int long long
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
using pibii = tuple<int,bool,int,int>;
#define endl '\n'
#define f first
#define s second

int const N = 100010;

int dp[N];

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(dp,-1,sizeof dp);
    int n;cin >> n;
    vector<pibii> vc;
    for(int i = 0;i < n;i++){
        int a,b,c;cin >> a >> b >> c;
        vc.emplace_back(b,false,-a,-c);
    }
    int m;cin >> m;
    for(int j = 0;j < m;j++){
        int a,b,c;cin >> a >> b >> c;
        vc.emplace_back(b,true,a,c);
    }
    sort(vc.begin(),vc.end());
    int sum = 0;
    dp[0] = 0;
    // for(auto [a,b,c,d]:vc){
    //     cout << a << " " << b << " " << c << " " << d << endl;
    // }
    for(auto [a,b,c,d]:vc){
        //cout << a << " " << b << " " << c << " " << d << endl;
        if(c > 0){
            for(int i = sum;i >= 0;i--){
                if(dp[i] != -1) dp[max(ll(0),i+c)] = max(dp[max(ll(0),i+c)],dp[i]+d);
            }
        }
        else{
            for(int i = 0;i <= sum;i++){
                if(dp[i] != -1) dp[max(ll(0),i+c)] = max(dp[max(ll(0),i+c)],dp[i]+d);
            }
        }
        // for(int i = 0;i <= sum+max(0,c);i++) cout << dp[i] << " ";
        // cout << endl;
        sum += max(ll(0),c);
    }
    cout << dp[0];
}
#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...