Submission #1209930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209930		cowwycow	Feast (NOI19_feast)	C++20	100 / 100	83 ms	12104 KiB

feast

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
#define endl "\n"
#define fi first
#define se second;
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
using ppii = pair<int, pii>;
using ull = unsigned long long;


const int N = 3e5 + 5;

int n, k;

ll a[N];

pll dp[N][2];

pll sus;

bool ck(ll mid){
	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 p1 = {dp[i - 1][0].first + a[i] - mid, dp[i - 1][0].second + 1};
		pll p2 = {dp[i - 1][1].first + a[i], dp[i - 1][1].second};
		dp[i][1] = max(p1, p2);
	}
	sus = max(dp[n][0], dp[n][1]);
	return sus.second >= k;
}

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)){
			l = mid;
		}else{
			r = mid - 1;
		}
	}

	ck(l);
	cout << sus.first + l * k;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	int test = 1;
	//cin >> test;
	while(test--){
		solve();
	}
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:63:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |                 freopen(name".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:64:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |                 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