Submission #1261343

#TimeUsernameProblemLanguageResultExecution timeMemory
1261343escobrandCloud Computing (CEOI18_clo)C++20
100 / 100
389 ms2056 KiB
#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<int,int> pii;

const int maxn = 2000 * 50 + 10;
const ll inf = 1e16;

int i,n,t,m,j;
struct bruh 
{
  int c,f,cost;
  bool operator < (const bruh & o)const 
  {
    if(f != o.f)return f > o.f;
    return cost < o.cost;
  }
  friend istream & operator >> (istream & inp,bruh& k){return inp>>k.c>>k.f>>k.cost,inp;}
}a[maxn];

bool check(const int &i)
{
  return i >= 0 && i < maxn;
}

ll dp[maxn][2],ans = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    cin>>n;
    
    for(i = 0;i<n;i++)
    {
      cin>>a[i];
      a[i].c = -a[i].c;
      a[i].cost = -a[i].cost;
    }
    
    cin>>m;
    
    for(i = n;i<n+m;i++)
    {
      cin>>a[i];
    }
    
    sort(a,a+n+m);
    
    bool now = 0,pre = 0;
    for(i = 1;i<maxn;i++)dp[i][0] = -inf;
    
    for(i = 0;i<n+m;i++)
    {
      now = !now;
      pre = !now;
      for(j = 0;j<maxn;j++)
      {
        dp[j][now] = dp[j][pre];
        if(check(j + a[i].c))dp[j][now] = max(dp[j][now],dp[j + a[i].c][pre] + a[i].cost);
        ans = max(ans,dp[j][now]);
      }
    }
    
    cout<<ans;
    
    
    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...