Submission 1705 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1705	12/06/2013 20:22:00	rlac	A - Dos es mejor que una	Accepted	109	9.3 KiB	Java 1.8

Code

import java.util.*;
import java.io.*;

public class Main implements Runnable {
	public static void main(String[] args) {
		new Thread(new Main()).start();
	}

BufferedReader br;

StringTokenizer st;

PrintWriter out;

boolean eof;

public void run() {
		try {
			Locale.setDefault(Locale.US);
			//br = new BufferedReader(new FileReader(FNAME + ".in"));
            br = new BufferedReader(new InputStreamReader(System.in));
			//out = new PrintWriter(FNAME + ".out");
            out = new PrintWriter(System.out);
			solve();
		} catch (IOException e) {
		} finally {
			out.close();
		}
	}

String nextToken() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				eof = true;
				return "0";
			}
		}
		return st.nextToken();
	}

int nextInt() {
		return Integer.parseInt(nextToken());
	}

long nextLong() {
		return Long.parseLong(nextToken());
	}

double parseDouble() {
		return Double.parseDouble(nextToken());
	}

String FNAME = "oaks";

void myAssert(boolean e, String msg) {
		if (!e) {
			throw new Error(msg);
		}
	}

boolean[][] u, cD;
	int[][] W;
	int[] a;
	
	boolean canDel(int l, int r) {
		if (!u[l][r]) {
			u[l][r] = true;
			if (r - l < 2) {
				cD[l][r] = true;
				u[l][r] = true;
			} else {
				cD[l][r] = false;
				for (int i = l + 1; i < r; ++i) {
					if (canDel(l, i) && canDel(i, r) && ((a[l] - a[i]) * (a[i] - a[r]) < 0)) {
						cD[l][r] = true;
						W[l][r] = i;
						break;
					}
				}
			}
		}
		return cD[l][r];
	}

void write(int l, int r) {
		if (r - l < 2) return;
		write(l, W[l][r]);
		write(W[l][r], r);
		out.println(W[l][r] + 1);
	}
	
	public void solve() throws IOException {
		int n = nextInt();
		a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}

u = new boolean[n][n];
		cD = new boolean[n][n];
		W = new int[n][n];
		
		int[] D = new int[n];
		int[] p = new int[n];
		D[0] = 1;
		p[0] = -1;
		for (int i = 1; i < n; i++) { 
			for (int j = 0; j < i; j++) {
				if (a[i] >= a[j] && D[j] > 0 && canDel(j, i)) {
					if (D[j] + 1 > D[i]) {
						D[i] = D[j] + 1;
						p[i] = j;
					}
				}
			}
		}
		if (D[n - 1] == 0) {
			out.println(-1);
			return;
		}
		out.println(n - D[n - 1]);
		boolean[] leave = new boolean[n];
		int f = n - 1;
		while (f >= 0) {
			leave[f] = true;
			f = p[f];
		}
		
		
		f = 0;
		for (int i = 1; i < n; i++) {
			if (leave[i]) {
				write(f, i);
				f = i;
			}
		}
		
	}

}

Judgement Details

Test 01: 1.129 0.078 8608K ok
Test 02: 0.155 0.078 9072K ok
Test 03: 0.148 0.047 9068K ok
Test 04: 0.182 0.062 9060K ok
Test 05: 0.153 0.047 9060K ok
Test 06: 0.205 0.078 9536K ok
Test 07: 0.179 0.062 9480K ok
Test 08: 0.142 0.094 9544K ok
Test 09: 0.150 0.094 9560K ok
Test 10: 0.151 0.031 9548K ok
Test 11: 0.152 0.062 9556K ok
Test 12: 0.179 0.078 9536K ok
Test 13: 0.148 0.047 9516K ok
Test 14: 0.149 0.062 9540K ok
Test 15: 0.151 0.031 9540K ok
Test 16: 0.146 0.062 9496K ok
Test 17: 0.149 0.062 9540K ok
Test 18: 0.165 0.047 9544K ok
Test 19: 0.162 0.062 9560K ok
Test 20: 0.150 0.031 9480K ok
Test 21: 0.150 0.062 9544K ok
Test 22: 0.152 0.062 9540K ok
Test 23: 0.148 0.047 9232K ok
Test 24: 0.166 0.062 9540K ok
Test 25: 0.161 0.031 9540K ok
Test 26: 0.135 0.016 9064K ok
Test 27: 0.137 0.000 9064K ok
Test 28: 0.149 0.062 9064K ok
Test 29: 0.151 0.078 9064K ok
Test 30: 0.165 0.031 9092K ok
Test 31: 0.165 0.109 9540K ok
Test 32: 0.152 0.031 9540K ok
Test 33: 0.151 0.078 9544K ok
Test 34: 0.149 0.047 9540K ok
Test 35: 0.148 0.062 9532K ok
Test 36: 0.154 0.078 9536K ok
Test 37: 0.146 0.078 9532K ok
Test 38: 0.151 0.031 9540K ok
Test 39: 0.150 0.062 9536K ok
Test 40: 0.150 0.078 9532K ok
Test 41: 0.149 0.062 9556K ok
Test 42: 0.155 0.047 9540K ok
Test 43: 0.162 0.047 9536K ok
Test 44: 0.149 0.078 9540K ok
Test 45: 0.150 0.078 9532K ok
Test 46: 0.148 0.094 9548K ok
Test 47: 0.153 0.078 9556K ok
Test 48: 0.152 0.047 9560K ok
Test 49: 0.163 0.094 9536K ok
Test 50: 0.149 0.094 9560K ok
Accepted

Matcom Online Grader