結果
問題 | No.54 Happy Hallowe'en |
ユーザー | kuuso1 |
提出日時 | 2014-10-31 01:43:43 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 674 ms / 5,000 ms |
コード長 | 1,777 bytes |
コンパイル時間 | 810 ms |
コンパイル使用メモリ | 107,264 KB |
実行使用メモリ | 40,216 KB |
最終ジャッジ日時 | 2024-04-23 16:39:18 |
合計ジャッジ時間 | 5,320 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 21 ms
17,920 KB |
testcase_01 | AC | 21 ms
17,920 KB |
testcase_02 | AC | 22 ms
17,920 KB |
testcase_03 | AC | 23 ms
17,920 KB |
testcase_04 | AC | 166 ms
38,144 KB |
testcase_05 | AC | 245 ms
38,588 KB |
testcase_06 | AC | 332 ms
39,016 KB |
testcase_07 | AC | 451 ms
39,244 KB |
testcase_08 | AC | 551 ms
39,832 KB |
testcase_09 | AC | 674 ms
40,088 KB |
testcase_10 | AC | 22 ms
18,048 KB |
testcase_11 | AC | 21 ms
18,176 KB |
testcase_12 | AC | 620 ms
39,740 KB |
testcase_13 | AC | 611 ms
40,216 KB |
testcase_14 | AC | 22 ms
18,176 KB |
testcase_15 | AC | 22 ms
18,048 KB |
testcase_16 | AC | 22 ms
18,184 KB |
testcase_17 | AC | 23 ms
18,056 KB |
testcase_18 | AC | 24 ms
18,000 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+x.V>y.V+y.T?1:x.T+x.V<y.V+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));} }