oj.uz

Submission #766992

# Submission time Handle Problem Language Result Execution time Memory
766992 2023-06-26T09:58:58 Z Sarpa Cloud Computing (CEOI18_clo) C++17
18 / 100
 708 ms 3972 KB 
// 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], i}, {c[i], v[i]}});
  for(int i = 1; i <= m; i++)
    cust.push_back({{F[i], i}, {C[i], V[i]}});

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

  for(int j = 0; j < n; j++){
    int i = serv[j].F.S;
    f[i] = serv[j].F.F, c[i] = serv[j].S.F, v[i] = serv[j].S.S;
  }
  for(int j = 0; j < m; j++){
    int i = cust[j].F.S;
    F[i] = cust[j].F.F, C[i] = cust[j].S.F, V[i] = cust[j].S.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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 2 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 3420 KB Output is correct
5 Correct 404 ms 3596 KB Output is correct
6 Correct 708 ms 3972 KB Output is correct
7 Correct 695 ms 3924 KB Output is correct
8 Correct 671 ms 3944 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 13 ms 840 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -