Submission #1316858

#TimeUsernameProblemLanguageResultExecution timeMemory
1316858thuhienneCloud Computing (CEOI18_clo)C++20
100 / 100
176 ms1396 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

const int maxn = 2009;

int n,m;

struct core {
	int number,frame,cost;
	bool operator < (const core & other) {
		return frame > other.frame;
	}
} shop[maxn],customer[maxn];

int currmax;
ll dp[59 * maxn];
//dp i j: xet den i, dang co j core thi max cost la bn

void update(int changequan,int changecost) {
	if (changequan >= 0) {
		currmax += changequan;
		for (int i = currmax;i >= changequan;i--) dp[i] = max(dp[i],dp[i - changequan] + changecost);
	} else {
		for (int i = 0;i <= currmax;i++) dp[i] = max(dp[i],dp[i - changequan] + changecost);
	}
	
//	for (int i = 0;i <= currmax;i++) cout << dp[i] << " ";
//	cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	
	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> shop[i].number >> shop[i].frame >> shop[i].cost;
	}
	sort(shop + 1,shop + 1 + n);
	
	cin >> m;
	for (int i = 1;i <= m;i++) {
		cin >> customer[i].number >> customer[i].frame >> customer[i].cost;
	}
	sort(customer + 1,customer + 1 + m);
//	re;
	
	memset(dp,-0x3f3f,sizeof(dp));
	
	dp[0] = 0;
	int pt = 0;
	for (int i = 1;i <= m;i++) {
		while (pt < n && shop[pt + 1].frame >= customer[i].frame) {
			pt ++;
			update(shop[pt].number,-shop[pt].cost);
		}
		
		update(-customer[i].number,customer[i].cost);
	
	}
	
	cout << *max_element(dp,dp + 1 + currmax);
	

}

/*
Aiming:
                                                           ==
                                                         +++++***
                                                        +:::::-=*
                                                         ------=
         ==========           ==================         --:--==              ============--
         ==========           ==-------=--:=--====       ---==++           ===========--====-=
        ==--========          ==--=================      =:::-=+          ==============----====
        ==:-=========         ===:===       =======      =::--=+         ========        ==--====
       ==--==========         ==-:===        =======     -:::-:=        =======           =======
      ==--:==  =======        ==--===        =======     =-:::-=        =======            =======
      =-.-===   =======       ==-====       =======     *:::----*       =======            =======
     ==--:==    =======       ==-==================     +-:::::-+       ======             =======
    ==-:-===     =======      ==--================     *=-:::::-=       =======            =======
    ==---===============      ==--=============        +--::---==*      ====--=            =======
   ===--=================     ==:-===                  =:-::::--=+      ====-===          =======
   ==.-===================    ==--===                  =::::::---+       ====---==      =========
  ==---==          =======    =======                 +-:---=====+        ==-===--==============
 =======            =======   =======                 =-:::::::--=+         =--=-=============
========             =======  =======                 =--::::::--=+           =============
                                                   ***++++++++++*****
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...