제출 #1341352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1341352		manubn	Split the sequence (APIO14_sequence)	Java	컴파일 에러	0 ms	0 KiB

sequence

/* ----------------------------------------------------------------------------  */
/*   ( The Authentic JAVA/Python/JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* --------------------------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj                        */
/*    Github : https://github.com/Manu577228                                  */
/*    Portfolio : https://manu-bharadwaj-portfolio.vercel.app/portfolio      */
/* -----------------------------------------------------------------------  */

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

public class Main {

    static int n, k;
    static int[][] where;
    static long[] pref, q;
    static long[][] dp;
    static int l = 1, r = 1;

    static boolean case1(int x, int y, int i) {
        return (dp[0][y] - dp[0][x] >= (pref[y] - pref[x]) * (pref[n] - pref[i]));
    }

    static boolean case2(int x, int y, int i) {
        return (dp[0][y] - dp[0][x]) * (pref[i] - pref[y]) <=
               (dp[0][i] - dp[0][y]) * (pref[y] - pref[x]);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        pref = new long[n + 1];
        dp = new long[2][n + 1];
        where = new int[k + 1][n + 1];
        q = new long[n + 5];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(st.nextToken());
            pref[i] = pref[i - 1] + x;
        }

        for (int i = 1; i <= k; i++) {
            q[r++] = 0;

            for (int j = 1; j <= n; j++) {

                while (r - l > 1 && case1((int)q[l], (int)q[l + 1], j)) l++;

                int x = (int)q[l];

                dp[1][j] = dp[0][x] + (pref[j] - pref[x]) * (pref[n] - pref[j]);
                where[i][j] = x;

                while (r - l > 1 && case2((int)q[r - 2], (int)q[r - 1], j)) r--;

                q[r++] = j;
            }

            l = 1;
            r = 1;

            for (int j = 1; j <= n; j++) {
                dp[0][j] = dp[1][j];
            }
        }

        long mx = -1;
        int idx = -1;

        for (int i = 1; i <= n; i++) {
            if (dp[0][i] > mx) {
                mx = dp[0][i];
                idx = i;
            }
        }

        out.println(mx);

        for (int i = 0; i < k; i++) {
            out.print(idx + " ");
            idx = where[k - i][idx];
        }

        out.println();
        out.flush();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.java:18: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error

=======