結果

問題 No.4 おもりと天秤
コンテスト
ユーザー ramia777
提出日時 2022-05-19 15:45:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,200 bytes
コンパイル時間 967 ms
コンパイル使用メモリ 90,336 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 18:47:01
合計ジャッジ時間 1,896 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//Yukicoder No.4
//重りと天秤


//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>//list
#include <set> //tree
#include <map> //連想配列
#include <unordered_set> //hash
#include <unordered_map> //hash
#include <algorithm>
#include <iomanip>
#include <string>
#include <stdlib.h>


using namespace std;
typedef unsigned long long ULL;
typedef signed long long SLL;
typedef unsigned int UINT;


int memo[2][100];
int N;
int W[100];


int possible = 0;
int _target_weight = 0;

//
// 半分の重さになるおもりの組み合わせがあるかを調べる
//
// n：おもりのインデックス
// total_weight:載せた合計の重さ
// flag :載せるとき1 載せないとき0
int func(int n, int total_weight, int flag)
{
	//cout << "n=" << n << ", total_weight = " << total_weight << endl;

	if (possible)
		return total_weight;

	if (n >= N)
		return total_weight;

	if (_target_weight < total_weight)
	{
		return total_weight;
	}

	if (_target_weight == total_weight)
	{
		possible = 1;
		return total_weight;
	}

	if (memo[flag][n])
		return memo[flag][n];

	memo[1][n] = func(n + 1, total_weight + W[n],1); //先に  n番目を載せた場合を調べる(探索枝を短くするため）
	memo[0][n] = func(n + 1, total_weight,0);        //後から n番目を載せなかった場合を調べる

	return total_weight;
}

//降順
int compare(const int * a, const int *b)
{
	if (*a < *b)
		return (1);
	else if (*a > *b)
		return (-1);
	return (0);
}

int main()
{
	int total = 0;

	cin >> N;

	for (int i=0;i<N;i++)
	{
		cin >> W[i];
		total += W[i];
	}

	
	if (total % 2)
	{
		//そもそも２分割できない合計だったらすぐさまimpossibleを返す
		cout << "impossible" << endl;
		return 0;
	}


	// 半分に割る
	_target_weight = total >> 1;

	//降順のソート
	qsort(W, N, sizeof(int), (int(*)(const void*, const void*))compare);


	//半分の重さになるかを深さ（再帰）探索。重たいものから載せる(探索枝を短くするため）
	func(0,0,1);

	
	if (possible == 1)
	{
		cout << "possible" << endl;
	}
	else
	{
		cout << "impossible" << endl;
	}

	//getchar();


	return 0;
}
0