Submission #1290618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290618		SmuggingSpun	Feast (NOI19_feast)	C++20	100 / 100	82 ms	11004 KiB

feast

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 3e5 + 5;
const ll INF = 1e18;
int n, k, a[lim];
namespace sub1{
	void solve(){
		cout << accumulate(a + 1, a + n + 1, 0LL);
	}
}
namespace sub3{
	void solve(){
		ll sum = 0, min_sum = 0, ans = 0;
		for(int i = 1; i <= n; i++){
			maximize(ans, (sum += a[i]) - min_sum);
			minimize(min_sum, sum);
		}
		cout << ans;
	}
}
namespace sub45{
	void solve(){
		vector<vector<ll>>dp(n + 1, vector<ll>(k + 1, -INF));
		dp[0][0] = 0;
		for(int i = 1; i <= n; i++){
			dp[i] = dp[i - 1];
			ll sum = 0;
			for(int j = i; j > 0; j--){
				sum += a[j];
				for(int t = 1; t <= k; t++){
					maximize(dp[i][t], dp[j - 1][t - 1] + sum);
				}
			}
		}
		cout << *max_element(dp[n].begin(), dp[n].end());
	}
}
namespace sub267{
	pair<ll, int>dp[lim][2];
	void solve(){
		dp[0][0] = make_pair(0, 0);
		dp[0][1] = make_pair(-INF, 0);
		function<pair<ll, int>(ll)>get = [&] (ll lambda){
			for(int i = 1; i <= n; i++){
				dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
				dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - lambda, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
			}
			return max(dp[n][0], dp[n][1]);
		};
		ll low = 1, high = INF, best_lambda = 0;
		while(low <= high){
			ll mid = (low + high) >> 1LL;
			if(get(mid).second >= k){
				low = (best_lambda = mid) + 1;
			}
			else{
				high = mid - 1;
			}
		}
		cout << get(best_lambda).first + best_lambda * k;		
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	if(*min_element(a + 1, a + n + 1) > -1){
		sub1::solve();
	}
	else if(k == 1){
		sub3::solve();
	}
	else if(max(n, k) <= 300){
		sub45::solve();
	}
	else{
		sub267::solve();
	}
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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