제출 #807996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807996		gun_gan	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1156 ms	3632 KiB

clo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 4005, C = 50;
int N, M;
vector<array<int,3>> a;

ll dp[2][MX * C];

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      for(int i = 0; i < MX * C; i++) 
            dp[0][i] = dp[1][i] = -1e18;
      
      cin >> N;
      for(int i = 1; i <= N; i++) {
            int c, f, v;
            cin >> c >> f >> v;
            a.push_back({f, c, -v});
      }

      cin >> M;

      for(int i = 1; i <= M; i++) {
            int c, f, v;
            cin >> c >> f >> v;
            a.push_back({f, -c, v});
      }

      sort(a.rbegin(), a.rend());

      dp[0][0] = 0;
      for(int i = 0; i < N + M; i++) {
            auto [f, c, v] = a[i];
            int k = i & 1;
            for(int j = 0; j < MX * C; j++) {
                  dp[k ^ 1][j] = dp[k][j];
                  if(j - c >= 0 && j - c < MX * C)
                        dp[k ^ 1][j] = max(dp[k ^ 1][j], dp[k][j - c] + v);
            }
      }

      cout << *max_element(dp[(N + M) & 1], dp[(N + M) & 1] + C * MX) << '\n';
}

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