Submission #535145

#	Time	Username	Problem	Language	Result	Execution time	Memory
535145		Aktan	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	32 ms	9620 KiB

Main

#include <bits/stdc++.h>
#define cerr cout
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define ft first
#define sc second
const int mod=1e9+7,INF=1e17,N=2e5+5;

int pr[N],sf[N],c[N],d[N];
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	vector<int> a(n+1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=n;i++){
		if(i==0){
			pr[i]=0;
			c[i]=a[i];
		}
		else{
			if(a[i]+pr[i-1]>a[i-1]+pr[i-1]){
				pr[i]=pr[i-1];
			}
			else
			{
				pr[i]=pr[i-1];
				pr[i]+=max((a[i-1]+pr[i-1]+1)-(pr[i-1]+a[i]),0ll);
			}
			c[i]=(a[i]+pr[i]);
		}
	}
	for(int i=n;i>=1;i--){
		if(i==n){
			sf[i]=0;
			d[i]=a[i];
		}
		else{
			if(a[i]+sf[i+1]>a[i+1]+sf[i+1]){
				sf[i]=sf[i+1];
			}
			else{
				sf[i]=sf[i+1];
				sf[i]+=max(0ll,(a[i+1]+sf[i+1]+1)-(sf[i]+a[i]));
			}
			d[i]=a[i]+sf[i];
		}
	}
	int ans=INF,res=INF;
	for(int i=1;i<=n;i++){
		if(i==1){
			if(ans>sf[i]){
				ans=sf[i];
			}
		}
		else if(i==n){
			if(ans>pr[i]){
				ans=pr[i];
			}
		}
		else{
			if(ans>max(pr[i],sf[i])){
				ans=max(pr[i],sf[i]);
			}
		}
	}
	cout << ans;
	
}

Compilation message (stderr)

Main.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:57:14: warning: unused variable 'res' [-Wunused-variable]
   57 |  int ans=INF,res=INF;
      |              ^~~

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60