結果

問題 No.393 2本の竹
ユーザー kuuso1kuuso1
提出日時 2016-07-12 01:15:07
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 174 ms / 1,000 ms
コード長 4,017 bytes
コンパイル時間 970 ms
コンパイル使用メモリ 116,340 KB
実行使用メモリ 27,076 KB
最終ジャッジ日時 2024-04-25 18:08:34
合計ジャッジ時間 3,025 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
25,180 KB
testcase_01 AC 23 ms
25,020 KB
testcase_02 AC 23 ms
24,916 KB
testcase_03 AC 23 ms
26,932 KB
testcase_04 AC 22 ms
24,628 KB
testcase_05 AC 24 ms
26,972 KB
testcase_06 AC 23 ms
25,144 KB
testcase_07 AC 24 ms
24,908 KB
testcase_08 AC 25 ms
22,708 KB
testcase_09 AC 174 ms
25,016 KB
testcase_10 AC 57 ms
22,588 KB
testcase_11 AC 79 ms
22,980 KB
testcase_12 AC 86 ms
26,956 KB
testcase_13 AC 64 ms
27,068 KB
testcase_14 AC 51 ms
24,844 KB
testcase_15 AC 35 ms
25,144 KB
testcase_16 AC 59 ms
25,036 KB
testcase_17 AC 23 ms
25,044 KB
testcase_18 AC 24 ms
25,184 KB
testcase_19 AC 23 ms
24,760 KB
testcase_20 AC 24 ms
27,076 KB
testcase_21 AC 23 ms
22,836 KB
testcase_22 AC 98 ms
27,068 KB
testcase_23 AC 61 ms
24,900 KB
testcase_24 AC 26 ms
26,968 KB
testcase_25 AC 24 ms
25,004 KB
testcase_26 AC 24 ms
24,772 KB
testcase_27 AC 145 ms
25,040 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		var sb = new StringBuilder();
		
		using (var r = new FastIn(1000000)){
			
			int T = r.ReadInt();
			for(;T>0;T--){
				int N1,N2;
				N1 = r.ReadInt(); N2 = r.ReadInt();
				int M = r.ReadInt();
				int[] A = new int[M];
				for(int i=0;i<M;i++) A[i] = r.ReadInt();
				
				Array.Sort(A);
				long sum = 0;
				
				bool[] dp = new bool[N1+1];
				
				dp[0] = true;
				int ans = 0;
				
				for(int i=0;i<M;i++){
					sum += A[i];
					for(int j=N1;j>=0;j--){
						if(!dp[j])continue;
						if(j+A[i] <=N1){
							dp[j+A[i]] = true;
						}
					}
					
					for(int j=0;j<=N1;j++){
						if(!dp[j])continue;
						if( sum - j <= N2){
							ans = Math.Max(ans,i+1);
						}
					}
				}
				sb.AppendLine(ans.ToString());
			}
		}
		Console.Write(sb.ToString());
	}
	public Sol(){
	}

	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(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}

class FastIn:IDisposable {
	int Size;
	byte[] Mem;
	int ptr;
	int rsize;
	bool unfinished;
	Stream stdin;
	void Init(int n) {
		Size = n;
		Mem = new byte[Size];
		rsize=(stdin=Console.OpenStandardInput()).Read(Mem, 0, Size);
		ptr = 0;
		unfinished=(rsize == Size);
	}
	void Next() {
		if (unfinished == false) return;
		rsize=stdin.Read(Mem, 0, Size);
		ptr = 0;
		unfinished = (rsize == Size);
	}
	
	~FastIn(){
		stdin.Dispose();
	}
	void IDisposable.Dispose(){
		stdin.Dispose();
	}
	public void Dispose(){
		stdin.Dispose();
	}
	
	public FastIn() {
		Init(100000);
	}
	public FastIn(int n) {
		Init(n);
	}
	public int ReadInt() {
		int ret = 0;
		int sig = 1;
		while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
			if(ret==0 && Mem[ptr] == '-'){
				sig *= -1; ptr++; continue;
			}
			ret = ret * 10 + Mem[ptr++] - '0';
			if (ptr == Size) Next();
		}
		while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
			ptr++;
			if (ptr == Size) Next();
		}
		return ret*sig;
	}
	public long ReadLong() {
		long ret = 0;
		long sig = 1;
		while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
			if(ret==0 && Mem[ptr] == '-'){
				sig *= -1; ptr++; continue;
			}
			ret = ret * 10 + Mem[ptr++] - '0';
			if (ptr == Size) Next();
		}
		while (ptr < rsize &&  (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r')  ) {
			ptr++;
			if (ptr == Size) Next();
		}
		return ret*sig;
	}
	public String ReadStr() {
		//2byte文字はNG
		StringBuilder sb = new StringBuilder();
		while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r') {
			sb.Append((char)Mem[ptr++]);
			if (ptr == Size && unfinished) Next();
		}
		while (ptr < rsize &&  (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
			ptr++;
			if (ptr == Size && unfinished) Next();
		}
		return sb.ToString();
	}
	public String ReadLine() {
		//極力使わない(split/parseするくらいなら上をつかう）
		StringBuilder sb = new StringBuilder();
		while (ptr < rsize && Mem[ptr] != '\n' && Mem[ptr] != '\r') {
			sb.Append((char)Mem[ptr++]);
			if (ptr == Size && unfinished) Next();
		}
		while (ptr < rsize &&  (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r')) {
			ptr++;
			if (ptr == Size && unfinished) Next();
		}
		return sb.ToString();
	}
}
0