oj.uz

Submission #119966

# Submission time Handle Problem Language Result Execution time Memory
119966 2019-06-22T19:32:26 Z raghav0307 Cloud Computing (CEOI18_clo) C++14
36 / 100
 425 ms 253028 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;

int memo[2*MAXN][2*MAXN];

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){
		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;
	for(int i = 0; i < n; i++){
		int c, f, vv;
		cin >> c >> f >> vv;
		v.push_back(Item(c, f, vv, 1));
	}
	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";
	// }
	cout << max(dp(0, 0), 0ll) << "\n";
	return 0;
}

Compilation message

clo.cpp: In function 'll dp(ll, ll)':
clo.cpp:40:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(pos == v.size()) return 0;
     ~~~~^~~~~~~~~~~
clo.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 126160 KB Output is correct
2 Correct 92 ms 126200 KB Output is correct
3 Correct 95 ms 126276 KB Output is correct
4 Correct 95 ms 126216 KB Output is correct
5 Correct 101 ms 126456 KB Output is correct
6 Correct 99 ms 126584 KB Output is correct
7 Correct 107 ms 126520 KB Output is correct
8 Correct 107 ms 126520 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 126148 KB Output is correct
2 Correct 94 ms 126216 KB Output is correct
3 Correct 93 ms 126344 KB Output is correct
4 Correct 95 ms 126208 KB Output is correct
5 Correct 157 ms 126360 KB Output is correct
6 Correct 108 ms 126300 KB Output is correct
7 Correct 237 ms 126516 KB Output is correct
8 Correct 193 ms 126396 KB Output is correct
9 Runtime error 400 ms 252824 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 94 ms 126200 KB Output is correct
2 Correct 97 ms 126188 KB Output is correct
3 Correct 98 ms 126232 KB Output is correct
4 Correct 96 ms 126164 KB Output is correct
5 Correct 100 ms 126280 KB Output is correct
6 Correct 99 ms 126200 KB Output is correct
7 Correct 102 ms 126300 KB Output is correct
8 Correct 96 ms 126312 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 126168 KB Output is correct
2 Correct 94 ms 126172 KB Output is correct
3 Runtime error 425 ms 252928 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 94 ms 126300 KB Output is correct
2 Correct 95 ms 126244 KB Output is correct
3 Correct 150 ms 126328 KB Output is correct
4 Correct 175 ms 126420 KB Output is correct
5 Correct 381 ms 126752 KB Output is correct
6 Runtime error 267 ms 253028 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 96 ms 126160 KB Output is correct
2 Correct 92 ms 126200 KB Output is correct
3 Correct 95 ms 126276 KB Output is correct
4 Correct 95 ms 126216 KB Output is correct
5 Correct 101 ms 126456 KB Output is correct
6 Correct 99 ms 126584 KB Output is correct
7 Correct 107 ms 126520 KB Output is correct
8 Correct 107 ms 126520 KB Output is correct
9 Correct 97 ms 126148 KB Output is correct
10 Correct 94 ms 126216 KB Output is correct
11 Correct 93 ms 126344 KB Output is correct
12 Correct 95 ms 126208 KB Output is correct
13 Correct 157 ms 126360 KB Output is correct
14 Correct 108 ms 126300 KB Output is correct
15 Correct 237 ms 126516 KB Output is correct
16 Correct 193 ms 126396 KB Output is correct
17 Runtime error 400 ms 252824 KB Execution killed with signal 11 (could be triggered by violating memory limits)