Submission #703318

#	Time	Username	Problem	Language	Result	Execution time	Memory
703318		MinhAnhnd	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	6 ms	11272 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define ll unsigned long long

using namespace __gnu_pbds;

#define modu 1000000007

typedef tree<long,null_type,less<long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;


//hyper_adj[a] -> b then (a before b)


#define sizeofA 200002

int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
    long N;
    long A[sizeofA] = {};
    long xuoi1[sizeofA] = {};
    long xuoi2[sizeofA] = {};
    long carry1[sizeofA] = {};
    long carry2[sizeofA] = {};
    long val1[sizeofA]= {};
    long val2[sizeofA]= {};
    long lefter = 0;
    long walter = 0;
    cin>>N;
    ll ans = 2000000000000000000;
    for (long i = 1;i<=N;i++){
        cin>>A[i];
        xuoi1[i] = max(xuoi1[i-1]+1,A[i]);
        long need = xuoi1[i] - A[i];
        if(A[i]>=A[i-1]) carry1[i] = max(need,carry1[i-1]);
        else {carry1[i]  = need; lefter += carry1[i-1];}
        val1[i] = lefter + carry1[i];
    }
    lefter = 0;
    for (long i = N;i>=1;i--){
        xuoi2[i] = max(xuoi2[i+1]+1,A[i]);
        long need = xuoi2[i] - A[i];
        if(A[i]>=A[i+1]) carry2[i] = max(need,carry2[i+1]);
        else {carry2[i]  = need; lefter += carry2[i+1];}
        val2[i] = lefter + carry2[i];
    }
    for (long i = 1;i<=N;i++){
        ans = min(ans, (ll)(val1[i]+val2[i] - min(carry1[i],carry2[i])));
    }
    cout<<ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:33:10: warning: unused variable 'walter' [-Wunused-variable]
   33 |     long walter = 0;
      |          ^~~~~~

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