Submission #1254636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254636		vibhas	Growing Vegetables is Fun 4 (JOI21_ho_t1)	Java	100 / 100	174 ms	34364 KiB

Main

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // number of plants
        int n = Integer.parseInt(br.readLine());
        // plant heights
        int[] plants = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            plants[i] = Integer.parseInt(st.nextToken());
        }
        br.close();
        // iterate, create L > R and R > L difference arrays
        long[] l_g_r = new long[n];
        long[] r_g_l = new long[n];
        for(int i = 0; i < n-1; i++){
            // if l > r
            if(plants[i] > plants[i+1]){
                l_g_r[i] = 0;
            }else{
                l_g_r[i] = plants[i+1]-plants[i]+1;
            }
        }
        l_g_r[n-1] = 0;
        for(int i = n-1; i > 0; i--) {
            // if r > l
            if(plants[i] > plants[i-1]){
                r_g_l[i] = 0;
            }else{
                r_g_l[i] = plants[i-1]-plants[i]+1;
            }
        }
        r_g_l[0] = 0;
        // pushing to right
        for(int i = 1; i < n; i++) {
            r_g_l[i] += r_g_l[i-1];
        }
        // pushing to left
        for(int i = n-2; i >= 0; i--){
            l_g_r[i] += l_g_r[i+1];
        }
        // find answer
        long min = 1000000000000000000L;
        for(int i = 0; i < n; i++){
            min = Math.min(min, Math.max(l_g_r[i], r_g_l[i]));
        }
        System.out.println(min);
    }
}

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