Submission #34258


Source Code Expand

Copy
import java.util.*;

public class Main{
	public static int solve(int[] data){
		boolean[] check = new boolean[data.length];
		int count = 0;
		for(int i = 0; i < data.length; i++){
			if( check[i] ){
				continue;
			}
			count++;
			Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
			List<Integer> temp = new ArrayList<Integer>();
			temp.add(i);
			map.put(1, temp);
			for(int j = i+1; j < data.length; j++){
				if( check[j] ){
					continue;
				}
				if( data[j] <= data[i] ){
					int t = map.size();
					for(int k = t-1; k >= 0; k--){
						List<Integer> list = new ArrayList<Integer>(map.get(k+1));
		//				System.out.println("list " + list);
						if( data[list.get(list.size()-1)] >= data[j] ){
							if( map.get(k+2) == null ){
			//					System.out.println("aha" + j);
								list.add(j);
								map.put(k+2, list);
			//					System.out.println(map);
							} else if( data[map.get(k+2).get(map.get(k+2).size()-1)] > data[j] ){
								list.add(j);
								map.put(k+2, list);
							}
						}
					}
		//			System.out.println(map);
				}
			}
//			System.out.println(map);
			for(Integer x : map.get(map.size())){
				check[x] = true;
			}
		}
		return count;
	}		
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int[] data = new int[n];
		for(int i = 0; i < n; i++){
			data[i] = stdIn.nextInt();
		}
		System.out.println(solve(data));
	}
}

Submission Info

Submission Time
Task C - 積み重ね
User eulerdora
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1504 Byte
Status AC
Exec Time 703 ms
Memory 20620 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 44
Set Name Test Cases
All 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 02_maxrnd_00.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_increase_00.txt, 03_increase_01.txt, 03_increase_02.txt, 04_decrease_00.txt, 04_decrease_01.txt, 04_decrease_02.txt, 05_same_00.txt, 05_same_01.txt
Case Name Status Exec Time Memory
00_min.txt AC 422 ms 20364 KB
00_sample_01.txt AC 429 ms 20376 KB
00_sample_02.txt AC 429 ms 20232 KB
00_sample_03.txt AC 427 ms 20372 KB
00_sample_04.txt AC 417 ms 20368 KB
00_sample_05.txt AC 428 ms 20236 KB
01_rnd_00.txt AC 464 ms 20244 KB
01_rnd_01.txt AC 416 ms 20220 KB
01_rnd_02.txt AC 424 ms 20360 KB
01_rnd_03.txt AC 425 ms 20364 KB
01_rnd_04.txt AC 418 ms 20240 KB
01_rnd_05.txt AC 429 ms 20236 KB
01_rnd_06.txt AC 433 ms 20356 KB
01_rnd_07.txt AC 436 ms 20364 KB
01_rnd_08.txt AC 430 ms 20360 KB
01_rnd_09.txt AC 438 ms 20368 KB
02_maxrnd_00.txt AC 484 ms 20364 KB
02_maxrnd_01.txt AC 439 ms 20368 KB
02_maxrnd_02.txt AC 428 ms 20360 KB
02_maxrnd_03.txt AC 443 ms 20380 KB
02_maxrnd_04.txt AC 499 ms 20412 KB
02_maxrnd_05.txt AC 433 ms 20360 KB
02_maxrnd_06.txt AC 649 ms 20360 KB
02_maxrnd_07.txt AC 425 ms 20368 KB
02_maxrnd_08.txt AC 477 ms 20364 KB
02_maxrnd_09.txt AC 483 ms 20488 KB
02_maxrnd_10.txt AC 464 ms 20372 KB
02_maxrnd_11.txt AC 432 ms 20356 KB
02_maxrnd_12.txt AC 457 ms 20360 KB
02_maxrnd_13.txt AC 476 ms 20356 KB
02_maxrnd_14.txt AC 444 ms 20380 KB
02_maxrnd_15.txt AC 484 ms 20364 KB
02_maxrnd_16.txt AC 511 ms 20352 KB
02_maxrnd_17.txt AC 428 ms 20312 KB
02_maxrnd_18.txt AC 439 ms 20360 KB
02_maxrnd_19.txt AC 433 ms 20360 KB
03_increase_00.txt AC 703 ms 20332 KB
03_increase_01.txt AC 449 ms 20384 KB
03_increase_02.txt AC 488 ms 20236 KB
04_decrease_00.txt AC 451 ms 20620 KB
04_decrease_01.txt AC 445 ms 20604 KB
04_decrease_02.txt AC 441 ms 20576 KB
05_same_00.txt AC 434 ms 20488 KB
05_same_01.txt AC 448 ms 20488 KB