Submission #505171

#	Time	Username	Problem	Language	Result	Execution time	Memory
505171		DanerZein	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	87 ms	8652 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n; cin>>n;
  vector<ll> x,y;
  ll ma=-1;
  for(int i=0;i<n;i++){
    ll a; cin>>a;
    x.push_back(a);
    y.push_back(a);
  }
  vector<ll> in,de;
  in.push_back(0);
  de.resize(n+1);
  ll ac=0;
  for(int i=1;i<n;i++){
    x[i]+=ac;
    if(x[i]<=x[i-1]){
      ac+=(x[i-1]-x[i])+1;
      x[i]=x[i-1]+1;
    }
    in.push_back(ac);
  }
  ac=0;
  for(int i=n-2;i>=0;i--){
    y[i]+=ac;
    if(y[i]<=y[i+1]){
      ac+=(y[i+1]-y[i])+1;
      y[i]=y[i+1]+1;
    }
    de[i]=ac;
    //cout<<ac<<" ";
  }
  //cout<<endl;
  ll res=1e14+1;
  for(int i=0;i<n;i++){
    ll rp=in[i];
    rp+=max((ll)0,de[i]-in[i]);
    res=min(res,rp);
  }
  cout<<res<<endl;
  /*ll res=1e14+1;
  for(int k=0;k<min((int)vma.size(),2);k++){
    int i=vma[k];
    ll ac=0;
    vector<ll> y=x;
    ll c=0;
    for(int j=1;j<=i;j++){
      if(y[j]<=y[j-1]){
	ac+=(y[j-1]-y[j])+1;
	c+=(y[j-1]-y[j])+1;
      }
    }
    y[i]+=ac;
    for(int j=i+1;j<n;j++){
      if(y[j-1]<=y[j]){
	c+=(y[j]-y[j-1])+1;
	ac=0;
	y[j-1]=y[j]+1;
      }
      if(y[j]+ac>=y[j-1]){
	ac=abs(y[j]-y[j-1])-1;
      }
      y[j]+=ac;
    }
    res=min(res,c);
  }
  cout<<res<<endl;*/
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:7:6: warning: unused variable 'ma' [-Wunused-variable]
    7 |   ll ma=-1;
      |      ^~

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