結果

問題 No.90 品物の並び替え
コンテスト
ユーザー mban
提出日時 2017-01-08 17:13:55
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 103 ms / 5,000 ms
コード長 1,831 bytes
コンパイル時間 1,057 ms
コンパイル使用メモリ 112,268 KB
実行使用メモリ 26,272 KB
最終ジャッジ日時 2024-12-17 18:05:22
合計ジャッジ時間 1,933 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;


class Magatro
{
    static int[,] AA;
    static int M,N;
    static int max = 0;
    static void Main()
    {
        string[] s = Console.ReadLine().Split(' ');
        N = int.Parse(s[0]);
        M = int.Parse(s[1]);
        AA = new int[N, N];
        for(int i = 0; i < M; i++)
        {
            s = Console.ReadLine().Split(' ');
            AA[int.Parse(s[0]), int.Parse(s[1])] = int.Parse(s[2]);
        }
        int[] S = new int[N];
        for(int i = 0; i < N; i++)
        {
            S[i] = i;
        }
        while (next_permutation(S))
        {
          //  Console.WriteLine(string.Join(" ",S.Select(i=>i.ToString())));
            max = Math.Max(max, Score(S));
        }
        Console.WriteLine(max);
    
    }
    static public bool next_permutation(int[] perm)

    {

        int n = perm.Length;

        int k = -1;

        for (int i = 1; i < n; i++)

            if (perm[i - 1] < perm[i])

                k = i - 1;

        if (k == -1)

        {
            for (int i = 0; i < n; i++)

                perm[i] = i;

            return false;
        }
        int l = k + 1;
        for (int i = l; i < n; i++)
            if (perm[k] < perm[i])
                l = i;
        int t = perm[k];
        perm[k] = perm[l];
        perm[l] = t;
        Array.Reverse(perm, k + 1, perm.Length - (k + 1));

        return true;
    }
    static int Score(int[] items)
    {
        int res = 0;
        for(int i = 0; i < N-1; i++)
        {
            for(int j = i + 1; j < N; j++)
            {
                res += AA[items[i], items[j]];
            }
        }
        return res;
    }
}
0