Submission #1268831

#TimeUsernameProblemLanguageResultExecution timeMemory
1268831keerayCloud Computing (CEOI18_clo)C++20
100 / 100
179 ms8400 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define task "KJUMP"
typedef pair<int,int> pii;
const int maxn=1e6,INF=1e18;
struct giatri{
    int m,f,c;
    int id;
};
bool cmp(giatri a,giatri b){
    return (a.f > b.f || (a.f == b.f && a.c < b.c));
}
int n,m;
giatri a[maxn];
int dp[maxn];
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n ;
    int curs = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i].m >> a[i].f >> a[i].c;
        a[i].c *= -1;
        a[i].id = i;
    }
    cin >> m;
    for(int i=n+1;i<=n+m;i++){
        cin >> a[i].m >> a[i].f >> a[i].c;
        a[i].id = i;
    }
    sort(a+1,a+n+m+1,cmp);
    fill(dp+1,dp+maxn,-INF);
    int cur = 0;
    for(int i=1;i<=n+m;i++){
        if(a[i].id <= n){
            for(int j=cur;j>=0;j--){
                dp[j+a[i].m] = max(dp[j+a[i].m],dp[j]+a[i].c);
            }
            cur += a[i].m;
        }else{
            for(int j=a[i].m;j<=cur;j++){
                dp[j-a[i].m] = max(dp[j-a[i].m],dp[j]+a[i].c);
            }
        }
    }
    cout << *max_element(dp,dp+cur+1);
    return 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...