Submission #1209935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209935		nub	Feast (NOI19_feast)	C++20	100 / 100	124 ms	12104 KiB

feast

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define psf push_front
#define ppf pop_front
#define ps push
#define pp pop
using namespace std;

string file_name = "";
string input_extension = "";
string output_extension = "";

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
	return uniform_int_distribution<ll>(l, r)(rng);
}

ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;

ll mulmod(ll a, ll b, ll MOD){
	return (a%MOD)*(b%MOD)%MOD;
}

ll binpow(ll a, ll b, ll MOD){
	ll res = 1, t = a % MOD, exp = b;
	while (exp > 0){
		if (exp & 1) res = mulmod(res, t, MOD);
		t = mulmod(t, t, MOD);
		exp >>= 1;
	}
	return res;
}

ll invmod(ll a, ll MOD){
	return binpow(a, MOD-2, MOD);
}

vector<ll> v;
vector<pair<ll, ll>> dp[2];
int n, k;

// fi: res, se: cnt
pair<ll, ll> calc(ll lmb){
	dp[0][0] = {0, 0};
	dp[1][0] = {v[0]-lmb, 1};
	
	for (int i=1; i<n; i++){
		if (dp[0][i-1].fi >= dp[1][i-1].fi){
			dp[0][i] = dp[0][i-1];
		}
		else {
			dp[0][i] = dp[1][i-1];
		}
		
		if (dp[0][i-1].fi-lmb >= dp[1][i-1].fi){
			dp[1][i] = {dp[0][i-1].fi - lmb + v[i], dp[0][i-1].se+1};
		}
		else {
			dp[1][i] = {dp[1][i-1].fi + v[i], dp[1][i-1].se};
		}
	}
	return max(dp[0][n-1], dp[1][n-1]);
}

void solve(){
	cin >> n >> k;
	v.resize(n);
	dp[0].resize(n);
	dp[1].resize(n);
	for (int i=0; i<n; i++) cin >> v[i];
	ll l = 0, r = 1e18, mid;
	pair<ll, ll> res;
	while (l < r){
		mid = (l+r+1)/2;
		res = calc(mid);
		if (res.se >= k) l = mid;
		else r = mid-1;
	}
	res = calc(l);
	cout << res.fi + l * res.se;
}

int main(){
	if (file_name.size() > 0){
		freopen((file_name+input_extension).c_str(), "r", stdin);
		freopen((file_name+output_extension).c_str(), "w", stdout);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t=1;
//	cin >> t;
	while (t--) solve();
}

Compilation message (stderr)

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