제출 #172082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172082		leejseo	Mountains (IOI17_mountains)	C++14	100 / 100	48 ms	14204 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int D[2005][2005];
// if j > i D[j][i] == 0

bool able(int i, int j, int k, vector<int> &y){
	ll ax = i, bx = j, cx = k;
	ll ay = y[i], by = y[j], cy = y[k];
	ll ret = ax*by + bx*cy + cx*ay;
	ret -= bx*ay + cx*by + ax*cy;
	return ret >= 0;
}

int maximum_deevs(vector<int> y){
	int n = (int) y.size();
	y.insert(y.begin(), 0);
	for (int i=1; i<=n; i++){
		//i is the last deev
		D[i][i] = D[i-1][i] = 1;
		int l = i-1;
		int inside = 0;
		for (int j=i-2; j>=1; j--){
			if (able(j, l, i, y)){ // j is visible
				inside += D[j+1][l-1];
				l = j;
			}
			D[j][i] = max(D[j][i-1], D[j][l-1]+inside+1);
		}
	}
	return D[1][n];
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30