제출 #756802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756802		TsotneSV	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	27 ms	6592 KiB

Main

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

using ll = long long;

#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define ins insert
#define endl "\n"
#define flush fflush(stdout)
#define deb(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x<<" "<<x<<endl
const ll INF=1e17,MOD=1e9+7,MAXN=3e5+5;

ll A[MAXN],pref[MAXN],suff[MAXN],add[MAXN]; 
int tt=1,n;
void solve(){
	
	add[0] = 0;
	
	cin>>n; A[0] = A[n+1] = -INF; pref[0] = suff[n+1] = 0; 
	for(int i=1;i<=n;i++) {
		cin>>A[i];
		
		pref[i] = pref[i-1] + max(0ll,A[i-1] - A[i] + 1);
		
		add[i] = add[i-1] + max(0ll,A[i-1] - A[i] + 1);
		
	}
	
	for(int i=n;i>=1;i--) {
		suff[i] = suff[i+1] + max(0ll,A[i+1] - A[i] + 1);
	}
	
	
	
	ll mn = INF;
	
	for(int i=1;i<=n;i++) {
		ll tmp = pref[i] + suff[i] - min(suff[i],add[i]);
		mn = min(mn,tmp);
	} deb(mn);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
  //  cin>>tt;
    while(tt--){
        solve();
    }
}

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