Submission #1190464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190464		Muhammad_Aneeq	Tortoise (CEOI21_tortoise)	C++20	8 / 100	0 ms	328 KiB

tortoise

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#warning check the output
using namespace std;
#define int long long
int const N=5e5+10;
pair<int,int> dp[N]={};
inline void solve()
{
	int n;
	cin>>n;
	int a[n+1]={};
	a[0]=0;
	long long f=0;
	vector<int>pl;
	vector<int>sh;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	sh.push_back(1);
	for (int i=1;i<=n;i++)
	{
		if (a[i]==-1)
			pl.push_back(i);
		else
		{
			sh.push_back(i);
			f+=a[i];
		}
	}
	dp[0]={0,0};
	for (int i=1;i<sh.size();i++)
	{
		dp[i].second=n+10;
		int z=lower_bound(begin(pl),end(pl),sh[i])-begin(pl);
		int md=n+10;
		if (z!=pl.size())
			md=min(md,abs(sh[i]-pl[z]));
		if (z!=0)
		{
			z--;
			md=min(md,abs(sh[i]-pl[z]));
		}
		for (int j=0;j<i;j++)
		{
			int tm=sh[i]-sh[j];
			if (dp[j].first>0)
			{
				tm=1e9;
				int z=lower_bound(begin(pl),end(pl),sh[j])-begin(pl);
				if (z!=pl.size())
					tm=abs(pl[z]-sh[j])+abs(pl[z]-sh[i]);
				if (z>0)
				{
					z--;
					tm=min(tm,abs(pl[z]-sh[j])+abs(pl[z]-sh[i]));
				}
			}
			int st=0,en=a[sh[i]]+1;
			while (st+1<en)
			{
				int mid=(st+en)/2;
				int to=(sh[i]-1)*2;
				int req=dp[j].second+tm+2*(mid-1)*md;
				if  (req<=to)
					st=mid;
				else
					en=mid;
			}
			if (dp[j].first+st>dp[i].first)
			{
				dp[i].first=dp[j].first+st;
				dp[i].second=dp[j].second+tm+2*(max(0ll,st-1))*md;
			}
			else if (dp[j].first+st==dp[i].first)
			{
				dp[i].second=min(dp[i].second,dp[j].second+tm+2*max(0ll,(st-1))*md);
			}
		}
	}
	int z=0;
	for (int i=1;i<sh.size();i++)
	{
		// cout<<dp[i].first<<' '<<dp[i].second<<endl;
		z=max(z,dp[i].first);
	}
	cout<<f-z<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

tortoise.cpp:9:2: warning: #warning check the output [-Wcpp]
    9 | #warning check the output
      |  ^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27