結果
| 問題 |
No.4 おもりと天秤
|
| コンテスト | |
| ユーザー |
 tetora1011
|
| 提出日時 | 2019-11-16 20:04:21 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 5,000 ms |
| コード長 | 7,381 bytes |
| コンパイル時間 | 2,711 ms |
| コンパイル使用メモリ | 118,556 KB |
| 実行使用メモリ | 27,316 KB |
| 最終ジャッジ日時 | 2024-09-25 04:25:46 |
| 合計ジャッジ時間 | 4,431 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
namespace No004
{
class Program
{
public static void Solve(Input input)
{
var n = input.NextInt();
var w = input.NextInt(n);
if (w.Sum() % 2 != 0)
{
Console.WriteLine("impossible");
return;
}
var h = w.Sum() / 2;
// [i][j]: iまでのおもりでjの重さを作成できるか
var dp = Utils.Create2DArray(n + 1, h + 1, false);
dp[0][0] = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= h; j++)
{
if (dp[i][j])
{
dp[i + 1][j] = true;
if (j + w[i] <= h)
{
dp[i + 1][j + w[i]] = true;
}
}
}
}
if (dp[n][h])
{
Console.WriteLine("possible");
}
else
{
Console.WriteLine("impossible");
}
}
#region Main
public static void Main(string[] args)
{
// 出力が少ないときはこれをセットする方が時間かかるけれど
// そのときにTLEするのはアルゴリズムが悪いせいだし、まあ良しとする
var needsFlushOutput = true;
if (needsFlushOutput)
{
// 細かく出力しないようにする
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
}
// 通常は引数無しで、ファイルから読み出したい場合はpath指定する
var input = new Input();
// 仮想的に標準入力をセットする
// テスト入力したまま提出することがままあるので……
#if DEBUG
input.SetText("");
#endif
Solve(input);
Console.Out.Flush();
}
#endregion
#region Competitive Template
#pragma warning disable CS0414
static readonly int MOD = (int)1e9 + 7;
static readonly int[] dx = { 1, 0, -1, 0 };
static readonly int[] dy = { 0, 1, 0, -1 };
/// <summary> 左上が原点 </summary>
static readonly char[] dir = { 'R', 'U', 'L', 'D' };
#pragma warning restore CS0414
public class Input
{
// 変な改行コードがたまに混じっているので、一応セパレート指定する
// スペース単独指定の方がもちろん早い
static readonly char[] separator = { ' ', '\r', '\n' };
readonly StreamReader sr;
readonly Queue<string> queue;
/// <summary>
/// 特定のファイルから読み出したい場合はpath指定する
/// </summary>
public Input(string path = "")
{
queue = new Queue<string>();
if (string.IsNullOrEmpty(path))
{ sr = new StreamReader(Console.OpenStandardInput()); }
else
{ sr = new StreamReader(path); }
}
/// <summary>
/// 入力予約
/// </summary>
public void SetText(IEnumerable<string> items)
{
foreach (var item in items)
SetText(item);
}
/// <summary>
/// 入力予約
/// </summary>
public bool SetText(string s)
{
if (string.IsNullOrEmpty(s))
return false;
foreach (var elem in s.Trim().Split(separator, StringSplitOptions.RemoveEmptyEntries))
queue.Enqueue(elem);
return true;
}
/// <summary>
/// 要素が存在するか
/// </summary>
public bool Any() => queue.Any() || Read();
/// <summary>
/// 内部queueに入力からの値をsplitして格納する
/// </summary>
bool Read()
{
if (!SetText(sr.ReadLine()))
return false;
if (!queue.Any())
return Read();
return queue.Any();
}
/// <summary>
/// 次のstringを一つ読み込む
/// </summary>
public string Next()
{
if (!queue.Any() && !Read())
return "";
return queue.Dequeue();
}
/// <summary>
/// 指定個数queueにたまるまでenqueueし続ける
/// </summary>
bool Accumulate(int n)
{
while (queue.Count() < n)
if (!Read())
return false;
return true;
}
public int NextInt() => int.Parse(Next());
public long NextLong() => long.Parse(Next());
public double NextDouble() => double.Parse(Next());
/// <summary>
/// n個の要素をparseして、それぞれにoffsetをaddした配列を返す
/// </summary>
T[] NextT<T>(int n, T offset, Func<string, T> parse, Func<T, T, T> add)
{
if (!Accumulate(n))
return null;
var a = new T[n];
for (int i = 0; i < n; i++)
a[i] = add(parse(queue.Dequeue()), offset);
return a;
}
public string[] Next(int n) => NextT(n, "", x => x, (x, y) => x);
public int[] NextInt(int n, int offset = 0) => NextT(n, offset, int.Parse, (x, y) => x + y);
public long[] NextLong(int n, long offset = 0) => NextT(n, offset, long.Parse, (x, y) => x + y);
public double[] NextDouble(int n, double offset = 0.0) => NextT(n, offset, double.Parse, (x, y) => x + y);
}
static class Utils
{
public static T Max<T>(params T[] objs) => objs.Max();
public static T Min<T>(params T[] objs) => objs.Min();
/// <summary>
/// vでfillされたT[d1][d2]配列を作成する
/// </summary>
public static T[][] Create2DArray<T>(int d1, int d2, T v)
{
return
Enumerable.Repeat(0, d1).Select(_ =>
Enumerable.Repeat(v, d2).ToArray()).ToArray();
}
/// <summary>
/// vでfillされたT[d1][d2][d3]配列を作成する
/// </summary>
public static T[][][] Create3DArray<T>(int d1, int d2, int d3, T v)
{
return
Enumerable.Repeat(0, d1).Select(_ =>
Enumerable.Repeat(0, d2).Select(__ =>
Enumerable.Repeat(v, d3).ToArray()).ToArray()).ToArray();
}
}
#endregion
}
}