結果
| 問題 | No.269 見栄っ張りの募金活動 |
| ユーザー |
 utaka
|
| 提出日時 | 2019-12-25 21:56:09 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 68 ms / 5,000 ms |
| コード長 | 23,521 bytes |
| コンパイル時間 | 2,828 ms |
| コンパイル使用メモリ | 118,488 KB |
| 実行使用メモリ | 39,388 KB |
| 最終ジャッジ日時 | 2024-10-01 06:51:53 |
| 合計ジャッジ時間 | 4,602 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 26 ms
25,900 KB |
| testcase_01 | AC | 27 ms
24,016 KB |
| testcase_02 | AC | 27 ms
23,732 KB |
| testcase_03 | AC | 28 ms
26,160 KB |
| testcase_04 | AC | 42 ms
29,360 KB |
| testcase_05 | AC | 28 ms
24,020 KB |
| testcase_06 | AC | 27 ms
23,896 KB |
| testcase_07 | AC | 68 ms
39,388 KB |
| testcase_08 | AC | 27 ms
24,152 KB |
| testcase_09 | AC | 28 ms
23,988 KB |
| testcase_10 | AC | 26 ms
24,012 KB |
| testcase_11 | AC | 30 ms
24,536 KB |
| testcase_12 | AC | 27 ms
25,808 KB |
| testcase_13 | AC | 33 ms
27,264 KB |
| testcase_14 | AC | 30 ms
23,864 KB |
| testcase_15 | AC | 32 ms
25,024 KB |
| testcase_16 | AC | 26 ms
23,856 KB |
| testcase_17 | AC | 26 ms
21,940 KB |
| testcase_18 | AC | 41 ms
28,888 KB |
| testcase_19 | AC | 32 ms
25,008 KB |
| testcase_20 | AC | 28 ms
21,944 KB |
| testcase_21 | AC | 28 ms
24,112 KB |
| testcase_22 | AC | 29 ms
24,404 KB |
| testcase_23 | AC | 27 ms
23,988 KB |
| testcase_24 | AC | 29 ms
25,908 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
// ReSharper disable ArrangeTypeMemberModifiers
// ReSharper disable ConvertIfStatementToSwitchStatement
// ReSharper disable FunctionRecursiveOnAllPaths
// ReSharper disable InconsistentNaming
// ReSharper disable InlineOutVariableDeclaration
// ReSharper disable InvertIf
// ReSharper disable JoinDeclarationAndInitializer
// ReSharper disable MemberCanBeMadeStatic.Global
// ReSharper disable MemberCanBeMadeStatic.Local
// ReSharper disable NonReadonlyMemberInGetHashCode
// ReSharper disable PossibleNullReferenceException
// ReSharper disable RedundantUsingDirective
// ReSharper disable SuggestVarOrType_BuiltInTypes
// ReSharper disable SuggestVarOrType_Elsewhere
// ReSharper disable TailRecursiveCall
// ReSharper disable UnusedMember.Global
// ReSharper disable UnusedMember.Local
// ReSharper disable UseObjectOrCollectionInitializert
#if true && UTAKA_LOCAL
//#if false
#define UTAKA_DEBUG
#endif
//#define TOPCODER
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
using static UtakaApp.Util;
namespace UtakaApp
{
public partial class Program
{
/*
https://yukicoder.me/problems/no/269
*/
public const string SiteName = "YukiCoder";
public const string ContestName = "269";
public const string ProblemName = "";
public const long Mod = 1000000007L;
public void Solve()
{
int N = cin.ReadInt;
int S = cin.ReadInt;
int K = cin.ReadInt;
int baseSum = 0;
for (int i = 0; i < N; i++)
{
baseSum += i * K;
}
if (S < baseSum)
{
cou.WriteLine(0);
return;
}
int targetSum = S - baseSum;
// dp[i][j] : jのi分割の総数
long[][] dp = JagArray2D<long>(N + 1, targetSum + 1);
dp[0][0] = 1;
for (int i = 1; i <= N; i++)
{
for (int j = 0; j <= targetSum; j++)
{
if (j - i >= 0)
{
dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % Mod;
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
long ans = dp[N][targetSum];
cou.WriteLine(ans);
}
}
//=========================================================================================
// Debug IO
//=========================================================================================
public partial class Program
{
//=========================================================================================
// Main
//=========================================================================================
private readonly ConsoleInput cin;
private readonly IConsole cou;
public Program(ConsoleInput cin, IConsole cou)
{
this.cin = cin;
this.cou = cou;
}
#if !TOPCODER
public static void Main(string[] args)
{
#if UTAKA_LOCAL
//#if false
new TestCaseCheckerForAtCoder().TestProblems();
#else
var cin = new ConsoleInput(System.Console.In);
var console = new MyConsole();
new Program(cin, console).Solve();
console.Flush();
#endif
}
#endif
public void WriteEnumerable<T>(IEnumerable<T> A, string delimiter = " ")
{
if (!A.Any())
{
return;
}
var sb = new StringBuilder();
foreach (T v in A)
{
sb.Append(v);
sb.Append(delimiter);
}
if (sb.Length > 0)
{
sb.Length--;
}
cou.WriteLine(sb.ToString());
}
}
public static class Util
{
public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
while (low < high)
{
var mid = ((high - low) >> 1) + low;
if (comparer.Compare(arr[mid], value) < 0)
low = mid + 1;
else
high = mid;
}
return low;
}
public static int LowerBound<T>(T[] arr, T value) where T : IComparable
{
return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}
public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
while (low < high)
{
var mid = ((high - low) >> 1) + low;
if (comparer.Compare(arr[mid], value) <= 0)
low = mid + 1;
else
high = mid;
}
return low;
}
public static int UpperBound<T>(T[] arr, T value)
{
return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}
public static int UpperBound<T>(List<T> list, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
while (low < high)
{
var mid = ((high - low) >> 1) + low;
if (comparer.Compare(list[mid], value) <= 0)
low = mid + 1;
else
high = mid;
}
return low;
}
public static int UpperBound<T>(List<T> list, T value)
{
return UpperBound(list, 0, list.Count, value, Comparer<T>.Default);
}
public static T[] Array1D<T>(int a, T defaultValue)
where T : struct
{
var ret = new T[a];
for (int i = 0; i < a; i++)
{
ret[i] = defaultValue;
}
return ret;
}
public static T[] Array1D<T>(int a)
where T : struct
{
var ret = new T[a];
return ret;
}
/// <summary>
/// 要素数 (a, b) の、defaultValue で満たされた配列を作成します。
/// </summary>
/// <typeparam name="T">配列の型</typeparam>
/// <param name="a">1次元の要素数</param>
/// <param name="b">2次元の要素数</param>
/// <param name="defaultValue">デフォルト値</param>
/// <returns>指定した条件で初期化された配列</returns>
public static T[,] Array2D<T>(int a, int b, T defaultValue)
where T : struct
{
var ret = new T[a, b];
for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
ret[i, j] = defaultValue;
}
}
return ret;
}
public static T[,,] Array3D<T>(int a, int b, int c, T defaultValue)
where T : struct
{
T[,,] ret = new T[a, b, c];
for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
for (int k = 0; k < c; k++)
{
ret[i, j, k] = defaultValue;
}
}
}
return ret;
}
/// <summary>
/// 要素数 (a, b) の、defaultValue で満たされたJag配列を作成します。
/// </summary>
/// <typeparam name="T">配列の型</typeparam>
/// <param name="a">1次元の要素数</param>
/// <param name="b">2次元の要素数</param>
/// <param name="defaultValue">デフォルト値</param>
/// <returns>指定した条件で初期化された配列</returns>
public static T[][] JagArray2D<T>(int a, int b, T defaultValue)
where T : struct
{
var ret = new T[a][];
for (int i = 0; i < a; i++)
{
var row = new T[b];
ret[i] = row;
for (int j = 0; j < b; j++)
{
row[j] = defaultValue;
}
}
return ret;
}
/// <summary>
/// 要素数 (a, b) のdefault値で満たされたJag配列を作成します。
/// </summary>
/// <typeparam name="T">配列の型</typeparam>
/// <param name="a">1次元の要素数</param>
/// <param name="b">2次元の要素数</param>
/// <returns>初期化された配列</returns>
public static T[][] JagArray2D<T>(int a, int b)
where T : struct
{
var ret = new T[a][];
for (int i = 0; i < a; i++)
{
ret[i] = new T[b];
}
return ret;
}
public static T[][][] JagArray3D<T>(int a, int b, int c, T defaultValue)
where T : struct
{
var ret = new T[a][][];
for (int i = 0; i < a; i++)
{
T[][] aRow = new T[b][];
ret[i] = aRow;
for (int j = 0; j < b; j++)
{
T[] bRow = new T[c];
aRow[j] = bRow;
for (int k = 0; k < c; k++)
{
bRow[k] = defaultValue;
}
}
}
return ret;
}
public static T[][][] JagArray3D<T>(int a, int b, int c)
where T : struct
{
var ret = new T[a][][];
for (int i = 0; i < a; i++)
{
T[][] aRow = new T[b][];
ret[i] = aRow;
for (int j = 0; j < b; j++)
{
T[] bRow = new T[c];
aRow[j] = bRow;
}
}
return ret;
}
public static T[][][][] JagArray4D<T>(int a, int b, int c, int d, T defaultValue)
where T : struct
{
var ret = new T[a][][][];
for (int i = 0; i < a; i++)
{
T[][][] aRow = new T[b][][];
ret[i] = aRow;
for (int j = 0; j < b; j++)
{
T[][] bRow = new T[c][];
aRow[j] = bRow;
for (int k = 0; k < c; k++)
{
T[] cRow = new T[d];
bRow[k] = cRow;
for (int l = 0; l < d; l++)
{
cRow[l] = defaultValue;
}
}
}
}
return ret;
}
public static T[][][][] JagArray4D<T>(int a, int b, int c, int d)
where T : struct
{
var ret = new T[a][][][];
for (int i = 0; i < a; i++)
{
T[][][] aRow = new T[b][][];
ret[i] = aRow;
for (int j = 0; j < b; j++)
{
T[][] bRow = new T[c][];
aRow[j] = bRow;
for (int k = 0; k < c; k++)
{
T[] cRow = new T[d];
bRow[k] = cRow;
}
}
}
return ret;
}
public static T[][][][][] JagArray5D<T>(int a, int b, int c, int d, int e, T defaultValue)
where T : struct
{
var ret = new T[a][][][][];
for (int i = 0; i < a; i++)
{
T[][][][] aRow = new T[b][][][];
ret[i] = aRow;
for (int j = 0; j < b; j++)
{
T[][][] bRow = new T[c][][];
aRow[j] = bRow;
for (int k = 0; k < c; k++)
{
T[][] cRow = new T[d][];
bRow[k] = cRow;
for (int l = 0; l < d; l++)
{
T[] dRow = new T[e];
cRow[l] = dRow;
for (int m = 0; m < e; m++)
{
dRow[m] = defaultValue;
}
}
}
}
}
return ret;
}
public static T[][][][][] JagArray5D<T>(int a, int b, int c, int d, int e)
where T : struct
{
var ret = new T[a][][][][];
for (int i = 0; i < a; i++)
{
T[][][][] aRow = new T[b][][][];
ret[i] = aRow;
for (int j = 0; j < b; j++)
{
T[][][] bRow = new T[c][][];
aRow[j] = bRow;
for (int k = 0; k < c; k++)
{
T[][] cRow = new T[d][];
bRow[k] = cRow;
for (int l = 0; l < d; l++)
{
T[] dRow = new T[e];
cRow[l] = dRow;
}
}
}
}
return ret;
}
/// <summary>
/// ジャグ配列をコピーして返す。
/// </summary>
public static T[][] CopyJagArray2D<T>(T[][] source)
where T : struct
{
int len = source.Length;
T[][] dest = new T[len][];
for (int i = 0; i < len; i++)
{
T[] inner = source[i];
int innerLength = inner.Length;
T[] newer = new T[innerLength];
Array.Copy(inner, newer, innerLength);
dest[i] = newer;
}
return dest;
}
}
public static class UtakaExtentions
{
/// <summary>
/// IList<T>をコピーします
/// </summary>
public static T[] Copy<T>(this IList<T> a)
{
T[] ret = new T[a.Count];
for (int i = 0; i < a.Count; i++) ret[i] = a[i];
return ret;
}
/// <summary>
/// 2次元ジャグ配列をコピーして返す。
/// </summary>
public static T[][] Copy<T>(this T[][] source)
where T : struct
{
int len = source.Length;
T[][] dest = new T[len][];
for (int i = 0; i < len; i++)
{
T[] inner = source[i];
int innerLength = inner.Length;
T[] newer = new T[innerLength];
Array.Copy(inner, newer, innerLength);
dest[i] = newer;
}
return dest;
}
}
public class IntLargeComparer : IComparer<int>
{
public static IntLargeComparer Instance = new IntLargeComparer();
public int Compare(int x, int y)
{
return y - x;
}
}
public class LongLargeComparer : IComparer<long>
{
public static LongLargeComparer Instance = new LongLargeComparer();
public int Compare(long x, long y)
{
if (x > y) return -1;
if (x < y) return 1;
return 0;
}
}
public class ConsoleInput
{
private readonly char _separator = ' ';
private readonly TextReader _stream;
private readonly Queue<string> inputStream;
public ConsoleInput(TextReader stream, char separator = ' ')
{
_separator = separator;
_stream = stream;
inputStream = new Queue<string>();
}
public string Read
{
get
{
if (inputStream.Count != 0)
{
return inputStream.Dequeue();
}
var tmp = _stream.ReadLine().Split(_separator);
for (var i = 0; i < tmp.Length; ++i)
{
inputStream.Enqueue(tmp[i]);
}
return inputStream.Dequeue();
}
}
public string ReadLine => _stream.ReadLine();
public int ReadInt => int.Parse(Read);
public long ReadLong => long.Parse(Read);
public double ReadDouble => double.Parse(Read);
public string[] ReadStrArray(long N)
{
var ret = new string[N];
for (long i = 0; i < N; ++i)
{
ret[i] = Read;
}
return ret;
}
public int[] ReadIntArray(long N)
{
var ret = new int[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadInt;
}
return ret;
}
public int[] ReadIntArrayMinus1(long N)
{
var ret = new int[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadInt - 1;
}
return ret;
}
public long[] ReadLongArray(long N)
{
var ret = new long[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadLong;
}
return ret;
}
}
public interface IConsole
{
void Flush();
void Write(object obj);
void Write(string str);
void WriteLine(object obj);
void WriteLine(string str);
void WriteLine();
}
public class MyConsole : IConsole
{
public MyConsole()
{
var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
Console.SetOut(sw);
}
public void Flush()
{
Console.Out.Flush();
}
public void Write(object obj)
{
Write(obj.ToString());
}
public void Write(string str)
{
Console.Write(str);
}
public void WriteLine(object obj)
{
WriteLine(obj.ToString());
}
public void WriteLine(string str)
{
Console.WriteLine(str);
}
public void WriteLine()
{
Console.WriteLine();
}
}
#if UTAKA_LOCAL
public class DebugConsole : IConsole
{
private readonly StringBuilder mSb;
public DebugConsole()
{
mSb = new StringBuilder();
}
public void Flush()
{
// 何もしない
}
public void Write(object obj)
{
Write(obj.ToString());
}
public void Write(string str)
{
mSb.Append(str);
}
public void WriteLine(object obj)
{
WriteLine(obj.ToString());
}
public void WriteLine(string str)
{
mSb.AppendLine(str);
}
public void WriteLine()
{
mSb.AppendLine();
}
public string GetAllOutput()
{
return mSb.ToString();
}
}
#endif
#if UTAKA_LOCAL
public class TestCaseCheckerForAtCoder
{
private string GetDirectoryPath()
{
var problemPart = string.IsNullOrEmpty(Program.ProblemName)
? ""
: $"/{Program.ProblemName}";
return
$"{Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}";
}
private string GetInputFilePath(int testCaseNumber)
{
return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in";
}
private string GetOutputFilePath(int testCaseNumber)
{
return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out";
}
public bool TestProblem(int testCaseNumber)
{
var inputFilePath = GetInputFilePath(testCaseNumber);
var outputFilePath = GetOutputFilePath(testCaseNumber);
TextReader inputStream = new StreamReader(inputFilePath);
var cin = new ConsoleInput(inputStream);
var debugConsoleWriter = new DebugConsole();
new Program(cin, debugConsoleWriter).Solve();
var output = debugConsoleWriter.GetAllOutput();
TextReader outputStream = new StreamReader(outputFilePath);
var outputAnswer = outputStream.ReadToEnd();
Dbg.WriteLine(output);
Dbg.WriteLine(outputAnswer);
var isCorrect = output == outputAnswer;
return isCorrect;
}
public void TestProblems(int targetTestCaseNumber = -1)
{
if (targetTestCaseNumber >= 0)
{
Console.WriteLine($"!!!!!!!!!!!! Check TestCase {targetTestCaseNumber} !!!!!!!!!!");
}
bool isSuccessAll = true;
int testCaseNumber = 0;
while (true)
{
testCaseNumber++;
bool foundTargetTest = targetTestCaseNumber == testCaseNumber;
if (targetTestCaseNumber >= 0 && !foundTargetTest)
{
continue;
}
var inputFileName = GetInputFilePath(testCaseNumber);
if (!File.Exists(inputFileName))
{
break;
}
Console.WriteLine($"TestCase {testCaseNumber} =====================================================");
var result = TestProblem(testCaseNumber);
if (result)
{
Console.WriteLine("Success");
}
else
{
isSuccessAll = false;
Console.WriteLine("Failure *****");
}
if (foundTargetTest)
{
break;
}
}
if (isSuccessAll)
{
Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!");
}
}
}
#endif
public static class Dbg
{
[Conditional("UTAKA_DEBUG")]
public static void WriteLine(string str)
{
Console.WriteLine(str);
}
[Conditional("UTAKA_DEBUG")]
public static void WriteLine()
{
Console.WriteLine();
}
[Conditional("UTAKA_DEBUG")]
public static void Write(string str)
{
Console.Write(str);
}
}
}