Submission #1270355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270355		nai0610	Feast (NOI19_feast)	C++20	100 / 100	79 ms	12104 KiB

feast

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =3e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,k;
ll a[maxn];
pair<ll,int> f[maxn][2];
int main() {
    // freopen("../input.inp","r",stdin);
    // freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
	start=clock();
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	ll l=1,r=1e18;
	while (l<=r) {
		ll mid=(l+r)/2;
		f[1][1]={a[1]-mid,1};
		for (int i=2;i<=n;i++) {
			f[i][0]=max(f[i-1][0],f[i-1][1]);
			f[i][1]=max(make_pair(f[i-1][0].first+a[i]-mid,f[i-1][0].second+1),
						make_pair(f[i-1][1].first+a[i],f[i-1][1].second));
		}
		if (max(f[n][0],f[n][1]).second<k) r=mid-1;
		else l=mid+1;
	}
	ll res=l-1;
	f[1][1]={a[1]-res,1};
	for (int i=2;i<=n;i++) {
		f[i][0]=max(f[i-1][0],f[i-1][1]);
		f[i][1]=max(make_pair(f[i-1][0].first+a[i]-res,f[i-1][0].second+1),
					make_pair(f[i-1][1].first+a[i],f[i-1][1].second));
	}
	cout<<max(f[n][0],f[n][1]).first+res*k;
	end=clock();
	ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
	cerr<<dur<<'\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