oj.uz

Submission #120093

# Submission time Handle Problem Language Result Execution time Memory
120093 2019-06-23T10:12:38 Z raghav0307 Cloud Computing (CEOI18_clo) C++14
36 / 100
 1116 ms 3960 KB 
/*raghav0307 - Raghav Gupta*/

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

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll

struct Item{
	int c, f, v, prod;
	Item (int cc, int ff, int vv, int type) : 
			c(cc), f(ff), v(vv), prod(type) {}
};

bool custom(Item a, Item b){
	if(a.f < b.f)
		return false;
	if(a.f > b.f)
		return true;
	if(a.prod == 1)
		return true;
	return false;
}

vector<Item> v;

const int MAXN = 2e3 + 5;
const int MAXC = 50;
const int inf = 1e15;

int dp[MAXN*MAXC], dp2[MAXN*MAXC];

// int memo[MAXN + 500][800];

// int dp(int pos, int left){
// 	if(pos == v.size())	return 0;
// 	if(memo[pos][left] != -1)	return memo[pos][left];
// 	if(v[pos].prod == 1){
// 		if(left + v[pos].c >= 800)	memo[pos][left] = dp(pos + 1, left);
// 		return memo[pos][left] = max( dp(pos+1, left + v[pos].c) - v[pos].v, dp(pos+1, left)); 
// 	}
// 	else if(v[pos].prod == 2){
// 		if(v[pos].c <= left) return memo[pos][left] =  max(dp(pos + 1, left - v[pos].c) + v[pos].v, dp(pos +1 , left));
// 		return memo[pos][left] = dp(pos + 1, left);
// 	}
// }


signed main(){
	fast_io();
	// memset(memo, -1, sizeof(memo));
	int n;	cin >> n;
	int tCores = 0;
	for(int i = 0; i < n; i++){
		int c, f, vv;
		cin >> c >> f >> vv;
		v.push_back(Item(c, f, vv, 1));
		tCores += c;
	}
	int m;	cin >> m;
	for(int i = 0; i < m; i++){
		int c, f, vv;
		cin >> c >> f >> vv;
		v.push_back(Item(c, f, vv, 2));
	}
	sort(v.begin(), v.end(), custom);
	// for(auto x : v){
	// 	cout << x.c << " " << x.f << " " << x.v << " " << x.prod << "\n";
	// }
	for(int i = 0; i <= tCores; i++)	dp[i] = dp2[i] = 0;
	// if(v.back().prod == 2){
	// 	for(int i = v.back().c; i < MAXN*MAXC; i++){
	// 		dp[i] = v.back().v;
	// 	}
	// }
	// for(int i = 0; i < 25; i++){
	// 	cout << dp[i] << " ";
	// }cout << "\n";
	for(int i = n+m-1; i >= 0; i--){
		for(int j = 0; j <= tCores; j++){
			if(v[i].prod == 1 and j + v[i].c <= tCores){
				dp2[j] = max(dp[j + v[i].c] - v[i].v, dp2[j]);
				dp2[j] = max(dp2[j], dp[j]);
			}
			else if(v[i].prod == 2 and j >= v[i].c){
				dp2[j] = max(dp[j - v[i].c] + v[i].v, dp2[j]);
				dp2[j] = max(dp2[j], dp[j]);
			}
		}
		for(int j = 0; j <= tCores; j++)
			dp[j] = dp2[j];
		// for(int i = 0; i < 25; i++){
		// 	cout << dp[i] << " ";
		// }cout << "\n";
	}
	cout << max(dp[0], 0ll) << "\n";
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 57 ms 768 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 261 ms 1400 KB Output is correct
8 Correct 45 ms 760 KB Output is correct
9 Runtime error 431 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Runtime error 34 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 54 ms 768 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 932 ms 2124 KB Output is correct
6 Runtime error 1116 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 57 ms 768 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 261 ms 1400 KB Output is correct
16 Correct 45 ms 760 KB Output is correct
17 Runtime error 431 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)