Submission #756940

#	Time	Username	Problem	Language	Result	Execution time	Memory
756940		jamezzz	Tortoise (CEOI21_tortoise)	C++17	100 / 100	83 ms	9888 KiB

tortoise

//https://oj.uz/submission/680268

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 500005

int n,a[maxn],l[maxn],r[maxn],s[maxn];

int main(){
	sf("%d",&n);
	ll ans=0;
	for(int i=1;i<=n;++i){
		sf("%d",&a[i]);
		if(a[i]!=-1)ans+=a[i];
	}
	int p=-1,q=-1,y=-1;
	for(int i=1;i<=n;++i){
		if(a[i]==-1)p=i;
		else if(p!=-1)l[i]=p;
	}
	p=-1;
	for(int i=n;i>=1;--i){
		if(a[i]==-1)p=i;
		else if(a[i]){
			if(p!=-1)r[i]=p;
			if(q!=-1)s[i]=q;//next a[i]>0
			else y=i;//last a[i]>0
			q=i;
		}
	}
	map<int,int> mp;
	priority_queue<int> pq;
	ll sum=0;
	for(int i=1;i<=n;++i){
		if(a[i]<=0)continue;
		dbg("%d:\n",i);
		int d=INF;
		if(l[i])d=min(d,2*(i-l[i]));
		if(r[i])d=min(d,2*(r[i]-i));
		int f=d;//what is the cost if this guy does a walk?
		if(s[i]&&r[i]){//have a prev, have a right
			//if i have someone after me, walk is free but do one cycle
			if(s[i]<r[i])f=min(f,2*(r[i]-s[i]));
			//else if is last guy in range, one free walk
			else f=0;
		}
		if(i==y)f=0;//if its the last guy, set to 0
		--a[i];
		while(a[i]&&sum+(i-1)<=2*(i-1)){//do cycles
			mp[d]++;
			dbg("take cycle %d\n",d);
			sum+=d;
			--a[i];
		}
		if(a[i]){//can replace a bigger cycle with this cycle
			if(prev(mp.end())->fi>=d){
				mp[d]+=a[i];
				dbg("take a[i] more %d\n",d);
				sum+=(ll)d*a[i];
			}
			while(!mp.empty()&&sum+(i-1)>2*(i-1)){
				auto[a,b]=*prev(mp.end());
				if(sum-(ll)a*b+(i-1)>2*(i-1)){
					sum-=(ll)a*b;
					mp.erase(prev(mp.end()));
					dbg("remove %d %d\n",a,b);
				}
				else{
					ll diff=sum+(i-1)-2*(i-1);
					ll r=(diff-1)/a;
					sum-=(ll)a*r;
					mp[a]-=r;
					dbg("remove2 %d %d\n",r,a);
					break;
				}
			}
		}
		//try to add the cost of a walk?
		if(sum+(i-1)>2*(i-1)){
			if(prev(mp.end())->fi>=f){
				auto[a,b]=*prev(mp.end());
				sum-=a;
				dbg("remove one %d\n",a);
				if(--mp[a]==0)mp.erase(prev(mp.end()));
				sum+=f;
				mp[f]++;
				dbg("take %d\n",f);
			}
			
		}
		else{
			sum+=f;
			mp[f]++;
			dbg("take2 %d\n",f);
		}
	}
	for(auto[a,b]:mp)ans-=b;
	cout<<ans;
}

Compilation message (stderr)

tortoise.cpp: In function 'int main()':
tortoise.cpp:69:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  sf("%d",&n);
      |    ^
tortoise.cpp:72:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   sf("%d",&a[i]);
      |     ^

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