Submission #1117475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117475		secretwood01	Growing Vegetables is Fun 4 (JOI21_ho_t1)	Java	0 / 100	118 ms	11812 KiB

Main

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int N = Integer.parseInt(br.readLine());
        long [] Arr = new long[N];
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        for (int i=0;i<N;i++) {
            Arr[i] = Long.parseLong(st.nextToken());
        }
        long [] PVals = new long[N];
        long [] PAdd = new long [N];
        PVals[0] = Arr[0];
        PAdd[0] = 0;
        for (int i=1;i<N;i++) {
            PVals[i] = Arr[i]+PAdd[i-1];
            PAdd[i] = PAdd[i-1];
            if (PVals[i]<=PVals[i-1]) {
                PAdd[i]+=PVals[i-1]-PVals[i]+1;
                PVals[i] = PVals[i-1]+1;
            }
        }
        long [] SVals = new long[N];
        long [] SAdd = new long [N];
        SVals[N-1] = Arr[N-1];
        SAdd[N-1] = 0;
        for (int i=N-2;i>=0;i--) {
            SVals[i] = Arr[i]+SAdd[i+1];
            SAdd[i] = SAdd[i+1];
            if (SVals[i]<=SVals[i+1]) {
                SAdd[i] = SVals[i+1]-SVals[i]+1;
                SVals[i] = SVals[i+1]+1;
            }
        }
        long ans = Long.MAX_VALUE;
        for (int i=0;i<N;i++) {
            ans = Math.min(ans, Math.max(SAdd[i], PAdd[i]));
        }
        pw.println(ans);
        pw.close();
        br.close();
    }
}   

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