結果
問題 | No.54 Happy Hallowe'en |
ユーザー | kuuso1 |
提出日時 | 2014-10-31 01:12:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,761 bytes |
コンパイル時間 | 1,940 ms |
コンパイル使用メモリ | 107,996 KB |
実行使用メモリ | 47,076 KB |
最終ジャッジ日時 | 2023-08-28 23:35:44 |
合計ジャッジ時間 | 7,279 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 50 ms
22,828 KB |
testcase_01 | AC | 50 ms
20,692 KB |
testcase_02 | AC | 50 ms
22,852 KB |
testcase_03 | AC | 51 ms
18,584 KB |
testcase_04 | AC | 199 ms
44,420 KB |
testcase_05 | AC | 282 ms
44,768 KB |
testcase_06 | AC | 381 ms
44,744 KB |
testcase_07 | AC | 505 ms
44,756 KB |
testcase_08 | AC | 598 ms
42,840 KB |
testcase_09 | AC | 715 ms
42,952 KB |
testcase_10 | AC | 50 ms
22,788 KB |
testcase_11 | AC | 53 ms
20,756 KB |
testcase_12 | AC | 618 ms
47,076 KB |
testcase_13 | AC | 677 ms
47,044 KB |
testcase_14 | AC | 52 ms
22,732 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 54 ms
20,864 KB |
testcase_18 | AC | 54 ms
20,708 KB |
コンパイルメッセージ
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; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ Array.Sort(P,(x,y)=>x.T>y.T?1:x.T<y.T?-1:0); bool[][] dp=new bool[2][]; int now=0; int next=1; dp[0]=new bool[10001]; dp[0][0]=true; int maxx=0; for(int i=0;i<N;i++){ now=i%2; next=1-now; dp[next]=new bool[10001]; for(int j=0;j<10001;j++){ if(dp[now][j]){ dp[next][j]=true; if(j<P[i].T){ if(j+P[i].V<10000){ dp[next][j+P[i].V]=true; }else{ dp[next][10000]=true; maxx=Math.Max(maxx,j+P[i].V); } } } } } if(dp[next][10000]==true){ Console.WriteLine(maxx); return; } int max=0; for(int i=0;i<10000;i++){ if(dp[next][i])max=i; } Console.WriteLine(max); } int N; Pair[] P; public Sol(){ N=ri(); P=new Pair[N]; for(int i=0;i<N;i++){ P[i]=new Pair(ria()); } } class Pair{ public int V; public int T; public Pair(int[] in_){ V=in_[0];T=in_[1]; } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(){return Console.ReadLine().Split(' ');} static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));} static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));} static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));} }