Submission #650317

#	Time	Username	Problem	Language	Result	Execution time	Memory
650317		daria	Cloud Computing (CEOI18_clo)	C++14	54 / 100	465 ms	1364 KiB

clo

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

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

const int M = 1e5+7;
const ll INF = 1e18;

int main(){
 int n, m; cin >> n;
 vector<ar> v;
 for(int i=0; i<n; ++i){
  ar a; a[3] = 0;
  cin >> a[1] >> a[0] >> a[2];
  a[0] *= -1;
  v.push_back(a);
 }
 cin >> m;
 for(int i=0; i<m; ++i){
  ar a; a[3] = 1;
  cin >> a[1] >> a[0] >> a[2];
  a[0] *= -1;
  v.push_back(a);
 }
 sort(v.begin(), v.end());
 //ora sono sortati in ordine decrescente di f, ciascuna query può usare solo i pc prima
 vector<ll> dp(M, -1e18);
  dp[0] = 0;
 for(int i=0; i<n+m; ++i){
  if(v[i][3]){ // é una query, provo a vendergli tutti i core che richiede
   for(int j=0; j+v[i][1]<M; ++j) if(dp[j+v[i][1]] != -INF) dp[j] = max(dp[j], dp[j+v[i][1]] + v[i][2]);}
  else{ // é un pc, provo a vendere tutti i suoi core
   for(int j=M-1; j>=v[i][1]; --j) if(dp[j-v[i][1]] != -INF) dp[j] = max(dp[j], dp[j-v[i][1]] - v[i][2]); }
 }
 ll res = 0;
 for(int j=0; j<M; ++j) res = max(res, dp[j]);
 cout << res << endl;
}

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