Submission #1143859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143859		borisAngelov	Feast (NOI19_feast)	C++20	100 / 100	66 ms	12104 KiB

feast

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

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
#define int ll
const ll mod = 3e14 +7;
const int MAX_N = 3e5 + 42;

std::pair< ll, int > dp[MAX_N][2];
ll a[MAX_N];

	int n, k;

std::pair< ll, int > aliens( ll x ){

	dp[0][1] = make_pair( a[0] - x, 1 );
	dp[0][0] = std::make_pair( 0, 0 );

	for (int i=1;i<n;i++) {

		std::pair< ll, int > A;
		A.first = dp[i-1][1].first + a[i];
		A.second = dp[i-1][1].second;

		std::pair< ll, int > B;
		B.first = dp[i-1][0].first + a[i] - x;
		B.second = dp[i-1][0].second + 1;

		dp[i][1] = std::max( A, B );
		dp[i][0] = max( dp[i-1][0], dp[i-1][1]);
	}

	return max(dp[n-1][0],dp[n-1][1]);
}

signed main(){
#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	std::cin >> n >> k;

	for( int i=0 ; i < n ; i++ ) std::cin >> a[i];

	ll l = 0, r = mod;
	while( l != r-1 ) {
		ll mid = ( l + r ) >> 1;
		if (aliens(mid).second >= k) l = mid;
		else r = mid;
	}

	cout << aliens(l).first + l * k << "\n";

	return 0;
}

• 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