結果

問題 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;
		}
	}
}
0