結果
| 問題 | 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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
コンパイルメッセージ
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 TOPCODERusing 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 !TOPCODERpublic static void Main(string[] args){#if UTAKA_LOCAL//#if falsenew TestCaseCheckerForAtCoder().TestProblems();#elsevar cin = new ConsoleInput(System.Console.In);var console = new MyConsole();new Program(cin, console).Solve();console.Flush();#endif}#endifpublic 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;elsehigh = 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;elsehigh = 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;elsehigh = 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_LOCALpublic 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_LOCALpublic 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 !!!!!!!!!");}}}#endifpublic 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);}}}