結果

問題 No.332 数列をプレゼントに
ユーザー norioc
提出日時 2016-02-15 14:51:20
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 307 ms / 2,000 ms
コード長 3,300 bytes
コンパイル時間 851 ms
コンパイル使用メモリ 108,160 KB
実行使用メモリ 19,712 KB
最終ジャッジ日時 2024-12-24 08:31:42
合計ジャッジ時間 7,363 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Generic;
using System.Linq;
class Program {
static string ReadLine() { return Console.ReadLine(); }
static int ReadInt() { return int.Parse(ReadLine()); }
static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
static string[] ReadStrings() { return ReadLine().Split(); }
static void Output(int[] ar, List<long> es, long x) {
long sum = 0;
for (int i = 0; i < ar.Length; i++) {
int p = es.IndexOf(ar[i]);
if (p == -1) {
Console.Write("x");
}
else {
sum += ar[i];
Console.Write("o");
es.RemoveAt(p);
}
}
Console.WriteLine();
if (sum != x) {
Console.WriteLine("sum ");
Console.WriteLine("x : {0}", x);
Console.WriteLine("sum: {0}", sum);
}
if (es.Count > 0) {
Console.WriteLine("es ");
Console.WriteLine(string.Join(" ", es));
}
}
static void Calc(long x, int[] ar) {
var xs = ar.Select(e => (long)e).ToList();
xs.Sort();
var ys = new List<long>();
for (int i = 0; i < 20; i++) {
if (xs.Count == 0) break;
ys.Add(xs[xs.Count-1]);
xs.RemoveAt(xs.Count-1);
}
long sum = xs.Sum();
var dp = new bool[xs.Count, sum + 1];
if (xs.Count > 0)
dp[0, xs[0]] = true;
for (int i = 1; i < xs.Count; i++) {
for (long j = sum - xs[i]; j > 0; j--) {
if (dp[i-1, j]) {
dp[i, j] = true;
dp[i, j + xs[i]] = true;
}
}
}
var es = new List<long>(ys); // ys
for (int i = 0; i < (1 << ys.Count); i++) {
int p = 0;
long t = 0;
for (int j = 0; j < ys.Count; j++) {
if ((i & (1 << j)) > 0) {
t += ys[j];
es[p++] = ys[j];
if (t > x) break;
}
}
if (t == x) {
Output(ar, es.GetRange(0, p), x);
return;
}
else if (t < x) {
if (xs.Count > 0 && x - t < dp.GetLength(1) && dp[xs.Count-1, x - t]) {
var es2 = es.GetRange(0, p);
long rest = x - t;
for (int j = xs.Count-1; j >= 0; j--) {
if (rest == 0) break;
if (j == 0) {
if (rest != xs[0]) throw new Exception();
es2.Add(rest);
}
else if (!dp[j-1, rest]) {
es2.Add(xs[j]);
rest -= xs[j];
}
}
Output(ar, es2, x);
return;
}
}
}
Console.WriteLine("No");
}
static void Main() {
var ss = ReadStrings();
long x = long.Parse(ss[1]);
var xs = ReadInts();
Calc(x, xs);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0