Submission #1017317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017317		vjudge1	Feast (NOI19_feast)	C++14	100 / 100	119 ms	12368 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

const int maxn = 3e5 + 5;

ll n, k;
ll a[maxn];

pll dp[maxn][2];

pll ck(ll mid){
	dp[1][0] = {0, 0};
	dp[1][1] = {a[1] - mid, 1};
	for(int i = 2; i <= n; i++){
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		pll sus1 = {dp[i - 1][0].first + a[i] - mid, dp[i - 1][0].second + 1};
		pll sus2 = {dp[i - 1][1].first + a[i], dp[i - 1][1].second};
		dp[i][1] = max(sus1, sus2);
	}
	return max(dp[n][0], dp[n][1]);
}

void solve(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	ll l = 0, r = 1e18, mid;
	while(l < r){
		mid = (l + r + 1) / 2;
		if(ck(mid).second >= k){
			l = mid;
		}else{
			r = mid - 1;
		}
	}
	cout << ck(l).first + l * k;
}

int main(){
	file();
	solve();
}

Compilation message (stderr)

feast.cpp: In function 'void file()':
feast.cpp:11:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen(name".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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