제출 #1318120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318120		hasan	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	0 ms	332 KiB

Main

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

#define endl '\n'
#define dl double
#define int long long
#define ul uint_fast32_t
#define ll int_fast64_t
#define dll long double
#define ull uint_fast64_t
#define spektar this_thread::sleep_for(chrono::milliseconds(50))

void solve(){
    int n;
    cin >> n;
    vector<ll> k(n);
    for(auto& i:k) cin >> i;
    vector<ll> k1=k,k2=k;
    vector<ll> kk1(n);
    vector<ll> kk2(n);
    kk1[0]=0;
    kk2[n-1]=0;
    ll max1=0;
    for(int i=1; i<n; i++){
        ll s1=max(k1[i],k1[i-1]+1)-k1[i];
        k1[i]=max(k1[i],k1[i-1]+1);
        kk1[i]=s1;
    }
    for(int i=n-2; i>=0; i--){
        ll s1=max(k2[i],k2[i+1]+1)-k2[i];
        k2[i]=max(k2[i],k2[i+1]+1);
        kk2[i]=s1;
    }
    vector<ll> pref1(n+1),pref2(n+1);
    pref1[0]=0;
    pref2[n]=0;
    for(int i=0; i<n; i++){
        pref1[i+1]=pref1[i]+kk1[i];
    }
    for(int i=n-1; i>=0; i--){
        pref2[i]=pref2[i+1]+kk2[i];
    }
    ll min1=1000000000000000000;
    for(int i=0; i<n; i++){
        min1=min(min1,min(max(max(kk1[i],kk2[i]),pref1[i])+pref2[i+1],max(pref2[i+1],max(kk1[i],kk2[i]))+pref1[i]));
    }
    cout << min1 << endl;
}

signed main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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