제출 #1017706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017706		vjudge1	Feast (NOI19_feast)	C++17	30 / 100	42 ms	10584 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
//#define int long long
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 3e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int a[MAXN], n, k;
ll dp[2 * MAXN]; // i * 0 + 0, i * 0 + 1, i * 0 * 2, i * 0 + 3
int cnt[2 * MAXN];

char buf[1 << 24 | 1], *p1, *p2;
//#define gc() ((p1==p2)?(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2?EOF:*p1++):*p1++)
#define gc() getchar()
int R(){
	int x = 0, f = 0;
	char c = gc();
	while (!isdigit(c)){
		if (c == '-') f = 1;
		c = gc();
	}
	while (isdigit(c)){
		x = x * 10 + (c ^ 48);
		c = gc();
	}
	return f ? -x : x;
}

pair<ll, int> solve(ll lampda){
	dp[0 * 2 + 0] = 0;
	dp[0 * 2 + 1] = -lampda;
	cnt[0 * 2 + 0] = 0;
	cnt[0 * 2 + 1] = 1;
	for (int i = 1; i <= n; i++){
		dp[i * 2 + 0] = max(dp[(i - 1) * 2 + 0], dp[(i - 1) * 2 + 1]);
		dp[i * 2 + 1] = max(dp[(i - 1) * 2 + 0] + a[i] - lampda, dp[(i - 1) * 2 + 1] + a[i]);
		cnt[i * 2 + 0] = (dp[(i - 1) * 2 + 0] > dp[(i - 1) * 2 + 1] ? cnt[(i - 1) * 2 + 0] : cnt[(i - 1) * 2 + 1]);
		cnt[i * 2 + 1] = (dp[(i - 1) * 2 + 0] + a[i] - lampda > dp[(i - 1) * 2 + 2] + a[i] ? cnt[(i - 1) * 2 + 0] + 1 : cnt[(i - 1) * 2 + 1]);

		//dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		//dp[i][1] = max(make_pair(dp[i - 1][0].F + a[i] - lampda, dp[i - 1][0].S + 1), 
				//make_pair(dp[i - 1][1].F + a[i], dp[i - 1][1].S));
	}
	return max(pair<ll, int>(dp[n * 2 + 0], cnt[n * 2 + 0]), pair<ll, int>(dp[n * 2 + 1], cnt[n * 2 + 1]));
}

int32_t main(){
	n = R(), k = R();
	//cin >> n >> k;
	for (int i = 1; i <= n; i++){
		a[i] = R();
		//cin >> a[i];
	}
	ll lo = 0, hi = 3e12;
	while (hi - lo > 1){
		ll mi = (lo + hi) >> 1;
		if (solve(mi).S >= k){
			lo = mi;
		} else {
			hi = mi;
		}
	}
	cout << solve(lo).F + k * lo;
}

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