Submission #766999

#	Time	Username	Problem	Language	Result	Execution time	Memory
766999		Sarpa	Cloud Computing (CEOI18_clo)	C++17	18 / 100	709 ms	3940 KiB

clo

// Be nam KHODA
#include<bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define all(x) (x).begin(), (x).end()
#define F first
#define S second
const ll N = 2000 + 10, mod = 1e9 + 7, inf = 1e15, mx = 53;

int n, m;
int c[N], f[N], v[N], C[N], F[N], V[N];
ll dp[2][N][mx], pd[2][N][mx];

int32_t main(){
  cin.tie(0), ios::sync_with_stdio(0);
  cin >> n;
  
  for(int i = 1; i <= n; i++)
    cin >> c[i] >> f[i] >> v[i];
  cin >> m;
  for(int i = 1; i <= m; i++)
    cin >> C[i] >> F[i] >> V[i]; 

   vector<pair<pii, pii>> serv, cust;
  for(int i = 1; i <= n; i++)
    serv.push_back({{f[i], -v[i]}, {c[i], i}});
  for(int i = 1; i <= m; i++)
    cust.push_back({{F[i], -V[i]}, {C[i], i}});

  sort(all(serv)), sort(all(cust));

  for(int j = 0; j < n; j++){
    int i = serv[j].S.S;
    f[i] = serv[j].F.F, c[i] = serv[j].S.F, v[i] = -serv[j].F.S;
  }
  for(int j = 0; j < m; j++){
    int i = cust[j].S.S;
    F[i] = cust[j].F.F, C[i] = cust[j].S.F, V[i] = -cust[j].F.S;
  }
  
  for(int j = 1; j <= m; j++)
    pd[0][j][0] = V[j];

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      int st = i&1ll;
      for(int t = 0; t <= c[i]; t++){
        dp[st][j][t] = max(dp[st][j - 1][t], dp[st^1ll][j][c[i - 1]]);

        int w = 0;
        if(t == c[i]) w = -v[i];

        if(f[i] >= F[j]){
          if(t > C[j])
            dp[st][j][t] = max(dp[st][j][t], dp[st][j - 1][t - C[j]] + V[j] + w);
          else
            dp[st][j][t] = max(dp[st][j][t], pd[st^1ll][j][C[j] - t] + w);
        }
      }
      
      pd[st][j][0] = dp[st][j - 1][c[i]] + V[j];

      for(int t = 1; t <= C[j]; t++){
        pd[st][j][t] = max(pd[st^1ll][j][t], pd[st][j - 1][C[j - 1]]);

        if(f[i] >= F[j]){
          if(t >= c[i])
            pd[st][j][t] = max(pd[st][j][t], pd[st^1ll][j][t - c[i]] - v[i]);
          else
            pd[st][j][t] = max(pd[st][j][t], dp[st][j - 1][c[i] - t]- v[i] + V[j]);
        }
      }

    }
  } 
  cout << dp[n&1][m][c[n]] << endl;
  return 0;   
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 18 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10