結果

問題 No.357 品物の並び替え (Middle)
コンテスト
ユーザー Kilisame
提出日時 2016-06-14 15:43:28
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,714 bytes
コンパイル時間 2,438 ms
コンパイル使用メモリ 79,620 KB
実行使用メモリ 54,560 KB
最終ジャッジ日時 2024-10-09 13:33:18
合計ジャッジ時間 6,064 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 6 RE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static int n;

    private static int m;

    private static int[][] sumPointArray;

    private static List<int[]>[] takenPointArray;

    private static List<int[]>[] givenPointArray;

    private static List<Integer> sortedGoodsNumber;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = Integer.parseInt(cin.next());
        sumPointArray = new int[n][2];
        takenPointArray = new List[10];
        givenPointArray = new List[10];
        sortedGoodsNumber = new ArrayList<Integer>(n);
        m = Integer.parseInt(cin.next());
        for (int i = 0; i < m; i++) {
            int left = Integer.parseInt(cin.next());
            int right = Integer.parseInt(cin.next());
            int point = Integer.parseInt(cin.next());

            sumPointArray[left][0] += point;
            if (takenPointArray[left] == null) {
                takenPointArray[left] = new ArrayList<int[]>();
            }
            int[] takenPoint = {right, point};
            takenPointArray[left].add(takenPoint);

            sumPointArray[right][1] += point;
            if (givenPointArray[right] == null) {
                givenPointArray[right] = new ArrayList<int[]>();
            }
            int[] givenPoint = {left, point};
            givenPointArray[right].add(givenPoint);
        }
        cin.close();
        execute();
    }

    private static void execute() {
        int totalPoint = 0;
        while (sortedGoodsNumber.size() < n) {
            int maxDiff = -1;
            int maxDiffIndex = -1;
            for (int i = 0; i < n; i++) {
                if (sortedGoodsNumber.contains(i)) {
                    continue;
                }
                int diff = sumPointArray[i][0] - sumPointArray[i][1];
                if (diff > maxDiff) {
                    maxDiff = diff;
                    maxDiffIndex = i;
                }
            }
            sortedGoodsNumber.add(maxDiffIndex);
            totalPoint += sumPointArray[maxDiffIndex][0];
            if (takenPointArray[maxDiffIndex] != null) {
                for (int[] takenPoint : takenPointArray[maxDiffIndex]) {
                    sumPointArray[takenPoint[0]][1] -= takenPoint[1];
                }
            }
            if (givenPointArray[maxDiffIndex] != null) {
                for (int[] givenPoint : givenPointArray[maxDiffIndex]) {
                    sumPointArray[givenPoint[0]][0] -= givenPoint[1];
                }
            }
        }
        // System.out.println(sortedGoodsNumber);
        System.out.println(totalPoint);
    }

}
0