Submission #721050

#	Time	Username	Problem	Language	Result	Execution time	Memory
721050		NeroZein	Feast (NOI19_feast)	C++17	0 / 100	1 ms	596 KiB

feast

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

const int N = 2002;

int n, k;
int a[N]; 
long long cost;
pair<long long, int> dp[N];
pair<long long, int> solve () {
	memset(dp, 0, sizeof dp);
	for (int i = 1; i <= n; ++i) {
		dp[i] = dp[i - 1];
		for (int j = i - 1, s = a[i]; j >= 0; --j) {
			pair<long long, int> ex = make_pair(dp[j].first + s - cost, dp[j].second - 1); 
			dp[i] = max(dp[i], ex);
			s += a[j];
		}
		// cout << "C : " << cost << ' ' << "i : " << i << ' ' << "{" << dp[i].first << ", " << dp[i].second << "}" << '\n';
	}
	// cout << '\n';
	return dp[n];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i]; 
	}	
	pair<int, int> ans; 
	int bc = 0; 
	long long l = 0, r = 100;
	while (l < r) {
		cost = (l + r + 1) / 2;
		if (-solve().second >= k) {
			l = cost;
			ans = dp[n];
			bc = cost;
			// cout << "EWW " << cost << '\n';
		} else {
			r = cost - 1;
		}
	}
	cout << ans.first - ans.second * bc << '\n';
	return 0;
}

Compilation message (stderr)

feast.cpp: In function 'std::pair<long long int, int> solve()':
feast.cpp:11:25: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   11 |  memset(dp, 0, sizeof dp);
      |                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from feast.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29