結果

問題 No.90 品物の並び替え
ユーザー リチウム
提出日時 2014-12-07 19:42:39
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,480 ms / 5,000 ms
コード長 2,169 bytes
コンパイル時間 3,932 ms
コンパイル使用メモリ 78,756 KB
実行使用メモリ 46,132 KB
最終ジャッジ日時 2024-06-11 16:13:23
合計ジャッジ時間 7,079 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.*;
import java.lang.Math;
public class ppp {
            
  public static void main(String[] args) {
      MyScanner sc=new MyScanner();
     int n=sc.nextInt();
     int m=sc.nextInt();
     int item1[]=new int[m];
     int item2[]=new int[m];
     int score[]=new int[m];
     for(int i=0;i<m;i++){
         item1[i]=sc.nextInt();
         item2[i]=sc.nextInt();
         score[i]=sc.nextInt();
     }
     int k=1;
     int N=n;
     while(N>0){
        k*=N;
        N--;
     }
     int b[]=new int[n];
     int ans=0;
     for(int i=0;i<n;i++){
         b[i]=i;
     }
     for(int i=0;i<k;i++){
         int a[]=permutation(b,i,k);
         int s=0;
         for(int j=0;j<m;j++){
             int x=0;
             int y=0;
             for(int p=0;p<n;p++){
                 if(a[p]==item1[j])x=p;
                 if(a[p]==item2[j])y=p;
             }
             if(x<y)s+=score[j];
            
         }
         ans=Math.max(ans,s);
     }
     System.out.println(ans);
     
      
  }
static int[] permutation(int[] base, int x,int k) {
    int n = base.length;
    int ans[] = new int[n];
    if (n == 1)
        return base;
    else {
        ArrayList<Integer> B = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            B.add(base[i]);
        }
        k /= n;
        int N = n - 1;
        for (int i = 0; i < n - 1; i++) {
            ans[i] = B.get(x / k);
            B.remove(x / k);
            x %= k;
            k /= N;
            N--;
        }
        ans[n - 1] = B.get(0);
    }
    return ans;
}
}
class MyScanner {
    int nextInt() {
        try {
            int c = System.in.read();
            while (c != '-' && (c < '0' || '9' < c))
                c = System.in.read();
            if (c == '-')
                return -nextInt();
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = System.in.read();
            } while ('0' <= c && c <= '9');
            return res;
        } catch (Exception e) {
            return -1;
        }
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    String next() {
        try {
            StringBuilder res = new StringBuilder("");
            int c = System.in.read();
            while (Character.isWhitespace(c))
                c = System.in.read();
            do {
                res.append((char) c);
            } while (!Character.isWhitespace(c = System.in.read()));
            return res.toString();
        } catch (Exception e) {
            return null;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0