Submission #650321

#	Time	Username	Problem	Language	Result	Execution time	Memory
650321		daria	Cloud Computing (CEOI18_clo)	C++14	100 / 100	766 ms	2224 KiB

clo

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef array<ll, 4> ar;
// f, c, v, type

const ll INF = 1e18;

int main(){
 int n, m; cin >> n;
 vector<ar> v;
 for(int i=0; i<n; ++i){
  ar a; a[1] = 0;
  cin >> a[2] >> a[0] >> a[3];
  a[0] *= -1;
  v.push_back(a);
 }
 cin >> m; int M = 50*(n+m)+1;
 for(int i=0; i<m; ++i){
  ar a; a[1] = 1;
  cin >> a[2] >> a[0] >> a[3];
  a[0] *= -1;
  v.push_back(a);
 }
 sort(v.begin(), v.end());
 vector<ll> dp(M, -1e18);
  dp[0] = 0;
 for(int i=0; i<n+m; ++i){
  if(v[i][1]){ for(int j=0; j+v[i][2]<M; ++j) if(dp[j+v[i][2]] != -INF) dp[j] = max(dp[j], dp[j+v[i][2]] + v[i][3]);}
  else{ for(int j=M-1; j>=v[i][2]; --j) if(dp[j-v[i][2]] != -INF) dp[j] = max(dp[j], dp[j-v[i][2]] - v[i][3]); }
 }
 ll res = 0;
 for(int j=0; j<M; ++j) res = max(res, dp[j]);
 cout << res << endl;
}

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