結果

問題 No.90 品物の並び替え
ユーザー wolthgilwolthgil
提出日時 2016-05-17 20:40:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 400 ms / 5,000 ms
コード長 3,535 bytes
コンパイル時間 1,040 ms
コンパイル使用メモリ 98,192 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-15 22:49:43
合計ジャッジ時間 2,014 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 31 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 35 ms
5,376 KB
testcase_06 AC 24 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 400 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <sstream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <array>
#include <list>
#include <map>
#include <bitset>
#include <memory>
#include <algorithm>
#include <utility>
#include <numeric>

namespace Util
{

std::vector<std::string> Split(const std::string& str, const char delim);
std::string Itos(const int value);
std::string Ftos(const double value);
int Stoi(const std::string& buf);
double Stof(const std::string& buf);
std::vector<int> ConvertInt(const std::vector<std::string>& buffers);
std::vector<double> ConvertDouble(const std::vector<std::string>& buffers);

}// namespace Util


struct Data
{
	int first;
	int second;
	int score;
};

int Eval(const std::vector<Data>& table, const std::vector<int>& order)
{
	int ret = 0;

	for(int left = 0; left < static_cast<int>(order.size()); ++left)
	{
		for(int line = 0; line < static_cast<int>(table.size()); ++line)
		{
			if(order[left] == table[line].first)
			{
				for(int right = left + 1; right < static_cast<int>(order.size()); ++right)
				{
					if(order[right] == table[line].second)
					{
						ret += table[line].score;
						break;
					}
				}
			}
		}
	}


	return ret;
}

int main()
{
	// 入出力の速度向上
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::string buf;
	std::vector<std::string> buffers;

	std::vector<int> order;
	std::vector<Data> table;

	std::getline(std::cin, buf);
	buffers = Util::Split(buf, ' ');

	order.resize(Util::Stoi(buffers[0]));
	std::iota(order.begin(), order.end(), 0);

	table.resize(Util::Stoi(buffers[1]));
	for(auto it = table.begin(); it != table.end(); ++it)
	{
		std::getline(std::cin, buf);
		buffers = Util::Split(buf, ' ');
		it->first = Util::Stoi(buffers[0]);
		it->second = Util::Stoi(buffers[1]);
		it->score = Util::Stoi(buffers[2]);
	}

	// printf("order-----\n");
	// for(auto& value : order)
	// {
	// 	printf("%d ", value);
	// }
	// printf("\n");

	// printf("table-----\n");
	// for(auto& line : table)
	// {
	// 	printf("%5d %5d %5d\n", line.first, line.second, line.score);
	// }

	int max = 0;
	while(std::next_permutation(order.begin(), order.end()))
	{
		const int current = Eval(table, order);
		if(max < current)
		{
			max = current;
		}
		// for(auto& value : order)
		// {
		// 	printf("%d ", value);
		// }
		// printf("\n");
	}

	printf("%d\n", max);


	return 0;
}


namespace Util
{

std::vector<std::string> Split(const std::string& str, const char delim)
{
	std::istringstream iss(str);
	std::vector<std::string> ret;
	std::string tmp;

	while(std::getline(iss, tmp, delim))
	{
		ret.push_back(tmp);
	}

	return ret;
}

std::string Itos(const int value)
{
	std::ostringstream ostream;
	ostream << value;
	return ostream.str();
}

std::string Itof(const double value)
{
	std::ostringstream ostream;
	ostream << value;
	return ostream.str();
}

int Stoi(const std::string& buf)
{
	return std::atoi(buf.c_str());
}

double Stof(const std::string& buf)
{
	return std::atof(buf.c_str());
}

std::vector<int> ConvertInt(const std::vector<std::string>& buffers)
{
	std::vector<int> ret(buffers.size());

	for(int cur = 0; cur < static_cast<int>(ret.size()); ++cur)
	{
		ret[cur] = Stoi(buffers[cur]);
	}

	return ret;
}

std::vector<double> ConvertDouble(const std::vector<std::string>& buffers)
{
	std::vector<double> ret(buffers.size());

	for(int cur = 0; cur < static_cast<int>(ret.size()); ++cur)
	{
		ret[cur] = Stof(buffers[cur]);
	}

	return ret;
}

}// namespace Util
0