Submission #637846

#	Time	Username	Problem	Language	Result	Execution time	Memory
637846		Neos	Cloud Computing (CEOI18_clo)	C++14	100 / 100	2058 ms	4044 KiB

clo

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

#define ll long long
#define ar array

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 4e3 + 7, M = 50 + 7, MOD = 1e9 + 7;	

int n, m;
ll dp[N * M + M], prv[N * M + M];

struct item {
	int c, f, v;
	item() {}
	item(int c, int f, int v):
		c(c), f(f), v(v) {}
	bool operator<(const item &other) const {
		return (f == other.f ? c > other.c : f > other.f);
	}
} a[N];

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	if (fopen("test.inp", "r"))
		freopen("test.inp", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].c >> a[i].f >> a[i].v;
		a[i].v = -a[i].v;
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i + n].c >> a[i + n].f >> a[i + n].v;
		a[i + n].c = -a[i + n].c;
	}
	
	sort(a + 1, a + n + m + 1);	
	fill(prv, prv + N * M + M + 1, -1e18);
	prv[M] = 0;

	int st = 0;
	while (st + 1 < n + m && a[st + 1].c < 0 && a[st + 1].f > a[st + 2].f) ++st;
	for (int i = st; i < n + m; i++) {
		fill(dp, dp + N * M + M + 1, -1e18);
		for (int j = 0; j <= 50 * n; j++) if (prv[j + M] != -1e18) {
			// choose
			if (j + a[i + 1].c <= 50 * n) {
				maximize(dp[M + j + a[i + 1].c], prv[j + M] + a[i + 1].v);
			}
			// not choose
			maximize(dp[M + j], prv[j + M]);
		}
		swap(dp, prv);
	}
	ll ans = 0;
	for (int i = 0; i <= 50 * n; i++) {
		maximize(ans, prv[i + M]);
	}
	cout << ans;
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:36:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:49:6: warning: array subscript 228457 is outside array bounds of 'long long int [228456]' [-Warray-bounds]
   49 |  fill(prv, prv + N * M + M + 1, -1e18);
      |  ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:21:19: note: while referencing 'prv'
   21 | ll dp[N * M + M], prv[N * M + M];
      |                   ^~~
clo.cpp:55:7: warning: array subscript 228457 is outside array bounds of 'long long int [228456]' [-Warray-bounds]
   55 |   fill(dp, dp + N * M + M + 1, -1e18);
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:21:4: note: while referencing 'dp'
   21 | ll dp[N * M + M], prv[N * M + M];
      |    ^~

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