Submission #1175899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175899		VicBVic	Feast (NOI19_feast)	C++20	100 / 100	126 ms	9832 KiB

feast

#include <bits/stdc++.h>
using namespace std;
//#define TESTS

#define x first
#define y second
#define pii pair<int,int>
#define veci vector<int>
#define vecp vector<pii>
#define all(x) x.begin(), x.end()
#define pb(x,y) x.push_back(y)

#define int long long

const int maxn = 3e5+5;
const int maxb = 40;

int n,k, v[maxn];
//costul daca termini la i
int d[maxn], mxd[maxn], arrd[maxn];

bool good(int l)
{
	for(int i=0;i<n;i++)
	{
		d[i]=v[i]-l;
		mxd[i]=0;
		arrd[i]=1;
	}

	for(int i=1;i<n;i++)
	{
		if(d[i]<=d[i-1]+v[i])
		{
			d[i]=d[i-1]+v[i];
			arrd[i]=arrd[i-1];
		}

		if(d[i]<=d[mxd[i-1]]+v[i]-l)
		{
			d[i]=d[mxd[i-1]]+v[i]-l;
			arrd[i]=arrd[mxd[i-1]]+1;
		}

		mxd[i]=(d[i]>d[mxd[i-1]]) ? i : mxd[i-1];
	}

	return arrd[mxd[n-1]] >=k;
}

void solve()
{
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>v[i];

	int l=0;
	for(int b=(1ll<<maxb); b>0; b>>=1)
	{
		if(good(l+b)) l+=b;
	}

	good(l);

	cout<<d[mxd[n-1]]+l*arrd[mxd[n-1]]<<'\n';
}

int32_t main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int t=1;

	#ifdef TESTS
		cin>>t;
	#endif
	while(t--)
	{
		solve();
	}
	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