Submission #246184

#TimeUsernameProblemLanguageResultExecution timeMemory
246184tonowakCloud Computing (CEOI18_clo)C++14
100 / 100
899 ms2160 KiB
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	vector<tuple<int, int, int>> input;
	array<int, 2> sum_c = {{0, 0}};
	REP(iter, 2) {
		int n;
		cin >> n;
		while(n --> 0) {
			int c, f, v;
			cin >> c >> f >> v;
			sum_c[iter] += c;
			input.emplace_back(make_tuple(2 * f - iter, c, v));
		}
	}
	sort(input.rbegin(), input.rend());
	debug(sum_c);

	const int mx = sum_c[0] + 1;
	constexpr LL inf = LL(1e18);
	vector<LL> dp(mx, -inf);
	dp[0] = 0;

	for(auto [useless_f, c, v] : input) {
		if(useless_f % 2)
			c *= -1;
		else
			v *= -1;
		debug(c, v);

		vector<LL> nw = dp;
		REP(curr_c, mx)
			if(0 <= curr_c + c and curr_c + c < mx)
				nw[curr_c + c] = max(nw[curr_c + c], dp[curr_c] + v);
		dp = nw;
	}
	cout << *max_element(dp.begin(), dp.end()) << '\n';
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:59:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [useless_f, c, v] : input) {
           ^
#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...