제출 #1330949

#제출 시각아이디문제언어결과실행 시간메모리
1330949silver_bulletCloud Computing (CEOI18_clo)C++17
100 / 100
267 ms1280 KiB
#include<bits/stdc++.h> 
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Rand(long long l,long long r)
{
    uniform_int_distribution<long long> dist(l,r);
    return dist(rng); 
}
const int maxsize = 4e3 + 2;
array<int,4> a[maxsize]; 
bool cmp(array<int,4> x,array<int,4> y)
{
    return (x[1] > y[1] || (x[1] == y[1] && x[3] < y[3]));
}
const int maxc = (int)1e5 + 2;
long long dp[maxc]; 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;++i) 
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        a[i][3] = -1; 
    }
    int m;
    cin >> m;
    for(int i=1;i<=m;++i)
    {
        cin >> a[i+n][0] >> a[i+n][1] >> a[i+n][2];
        a[i+n][3] = 1;
    }
    n += m;
    sort(a+1,a+n+1,cmp);
    for(int i=0;i<=1e5;++i) dp[i] = -1e18;
    dp[0] = 0;
    int c_core = 0;
    for(int i=1;i<=n;++i)
    {
        if(a[i][3] == -1)
        {
            c_core += a[i][0];
            for(int j=c_core;j>=a[i][0];--j)
            if(dp[j-a[i][0]] != -1e18)
            dp[j] = max(dp[j],dp[j-a[i][0]] - a[i][2]); 
        }
        else 
        {
            for(int j=0;j<=c_core-a[i][0];++j)
            if(dp[j+a[i][0]] != -1e18)
            dp[j] = max(dp[j],dp[j+a[i][0]] + a[i][2]); 
        }
    }
    long long ans = 0;
    for(int i=0;i<=c_core;++i) ans = max(ans,dp[i]);
    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...