Submission #1307096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307096		dohyonne	Hokej (COCI17_hokej)	Java	72 / 120	321 ms	131072 KiB

hokej

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class hokej {
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()), N = Integer.parseInt(st.nextToken());
        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o2.K - o1.K;
            }
        });
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken()), I = Integer.parseInt(st.nextToken());
            pq.add(new Pair(i, K, I));
        }
        int[] fisrt = new int[7], t = new int[7], A = new int[7];
        int idx = 0;
        t[0] = M;
        long Z = 0;
        ArrayList<Pair> sub = new ArrayList<>();
        while (!pq.isEmpty()) {
            int I = pq.peek().I, K = pq.peek().K;
            if (t[idx] == M)
                ++idx;
            else if (t[idx] + I > M) {
                Z += (long) (M - t[idx]) * K;
                sub.add(new Pair(t[idx], A[idx], pq.peek().idx));
                I -= M - t[idx];
                ++idx;
            }
            if (idx == 7)
                break;
            Z += (long) I * K;
            if (t[idx] == 0) {
                fisrt[idx] = A[idx] = pq.peek().idx;
                t[idx] = I;
            } else {
                sub.add(new Pair(t[idx], A[idx], pq.peek().idx));
                A[idx] = pq.peek().idx;
                t[idx] += I;
            }
            pq.poll();
            if (pq.size() == 6 - idx) {
                while (!pq.isEmpty()) {
                    Z += (long) pq.peek().I * pq.peek().K;
                    fisrt[++idx] = pq.poll().idx;
                }
            }
        }
        sub.sort(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.idx - o2.idx;
            }
        });
        System.out.printf("%d\n%d %d %d %d %d %d\n", Z, fisrt[1], fisrt[2], fisrt[3], fisrt[4], fisrt[5], fisrt[6]);
        sb.append(sub.size()).append('\n');
        for (Pair P : sub)
            sb.append(P.idx).append(' ').append(P.K).append(' ').append(P.I).append('\n');
        System.out.print(sb);
    }
}

class Pair {
    int idx, K, I;

    Pair(int idx, int K, int I) {
        this.idx = idx;
        this.K = K;
        this.I = I;
    }
}

• Subtask 1: 72 / 120