oj.uz

Submission #240469

# Submission time Handle Problem Language Result Execution time Memory
240469 2020-06-19T17:02:21 Z flcat Split the sequence (APIO14_sequence) Java 11
50 / 100
 690 ms 131072 KB 
import java.io.*;
import java.util.*;

public class sequence {
    static int N,K;
    static long S[] = new long[100001];
    static long D[][] = new long[2][100001];
    static int OPT[][] = new int[201][100001];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Short.parseShort(st.nextToken());
        K = Short.parseShort(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= N ; i++) {
            S[i] = Short.parseShort(st.nextToken());
            S[i] += S[i-1];
        }
        solve();

        br.close();
        bw.flush();
        bw.close();
    }

    private static boolean canSkip(int k, int i, int j,int threshold) {
        return (D[(k-1)%2][i] - D[(k-1)%2][j] + S[N] * (S[j] - S[i]))
                <= threshold * (S[j] - S[i]);
    }

    private static boolean canRemoveLastCandidate(int k, int i, int j, int l) {
        return (D[(k-1)%2][i] - D[(k-1)%2][j] + S[N] * (S[j] - S[i])) * (S[l] - S[j])
                <= (D[(k-1)%2][j] - D[(k-1)%2][l] + S[N] * (S[l] - S[j])) * (S[j] - S[i]);
    }

    private static void dp(int k) {
        LinkedList<Integer> candid = new LinkedList<>();
        candid.addLast(k-1);

        for(int i = k ; i <= N ; i++) {
            while (candid.size() > 1 && canSkip(k, candid.getFirst(), candid.get(1), (int) S[i])) {
                candid.removeFirst();
            }
                int j = candid.getFirst();
                OPT[k][i] = j;
                D[(k%2)][i] = D[(k-1)%2][j] + S[i] * S[j] - S[N] * S[j] + S[N] * S[i] - (S[i] * S[i]);

            while (candid.size() > 1
                    && canRemoveLastCandidate(k, i, candid.getLast(), candid.get(candid.size()-2))) {
                candid.removeLast();
            }
            candid.addLast(i);
        }
    }
    private static Vector<Integer> backtrace(int ind) {
        Vector<Integer> ret = new Vector<>();
        new Vector();
        int k = K;
        while (k > 0) {
            ret.add(ret.size(),ind);
            ind = OPT[k--][ind];
        }
        Collections.reverse(ret);
     return ret;
    }
    private static void solve() throws IOException {
        for(int k = 1 ; k <= K ; k++) {
            Arrays.fill(D[k%2], 0);
            dp(k);
        }
        long ret = 0; int ind = 1;
        for(int i = 1 ; i <= N ; i++) {
            if(ret < D[K%2][i]) {
                ret = D[K%2][i];
                ind = i;
            }
        }
        bw.write(ret+"\n");
        Vector<Integer> opt = backtrace(ind);
        for(int x : opt) {
            bw.write(x+" ");
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 121240 KB contestant found the optimal answer: 108 == 108
2 Correct 361 ms 121400 KB contestant found the optimal answer: 999 == 999
3 Correct 275 ms 121208 KB contestant found the optimal answer: 0 == 0
4 Correct 262 ms 121536 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 324 ms 121468 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 239 ms 121228 KB contestant found the optimal answer: 1 == 1
7 Correct 255 ms 121400 KB contestant found the optimal answer: 1 == 1
8 Correct 331 ms 121160 KB contestant found the optimal answer: 1 == 1
9 Correct 290 ms 121384 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 291 ms 121324 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 323 ms 121544 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 311 ms 121316 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 343 ms 121532 KB contestant found the optimal answer: 140072 == 140072
14 Correct 255 ms 121092 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 370 ms 121204 KB contestant found the optimal answer: 805 == 805
16 Correct 270 ms 121244 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 287 ms 121532 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 121728 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 361 ms 121396 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 267 ms 121396 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 307 ms 121440 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 256 ms 121264 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 302 ms 121508 KB contestant found the optimal answer: 933702 == 933702
7 Correct 301 ms 121200 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 320 ms 121300 KB contestant found the optimal answer: 687136 == 687136
9 Correct 288 ms 121348 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 299 ms 121408 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 121476 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 253 ms 121468 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 339 ms 121976 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 274 ms 121452 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 352 ms 121968 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 314 ms 122040 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 361 ms 121960 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 305 ms 121196 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 321 ms 121436 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 288 ms 121516 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 121608 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 402 ms 121956 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 449 ms 123952 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 320 ms 121616 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 521 ms 124144 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 396 ms 124164 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 479 ms 124160 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 434 ms 123976 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 402 ms 122120 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 458 ms 123160 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 123832 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 460 ms 124456 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Runtime error 690 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 364 ms 121404 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -