글 읽기 - 4퍼 터지는 예외 ㅜ

rlarlvy153 6년 전 0

dp left right로 풀어봤습니다만

4퍼에서 계속 죽네요

혹시 예외케이스가 있을까요?

#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>


using namespace std;
#define ll long long

vector<ll> v;
int n;
int candy;
ll elapsed[310][310][2];
ll can[310][310][2];

ll relu(ll a) {
	return a > 0 ? a : 0;
}
ll max3(ll a, ll b, ll c) {
	return max(max(a, b), c);
}

int dfs(int left, int right, int elap) {
	if (left < 0) return 0;
	if (right >= n) return 0;


}
int main() {

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif

	cin >> n;
	cin >> candy;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++) {
		elapsed[i][i][0] = elapsed[i][i][1] = abs(v[i]);
		can[i][i][0] = can[i][i][1] = relu(candy - abs(v[i]));
	}

	
	for (int size = 1; size < n; size++)
	{
		for (int i = 0; i + size < n; i++) {
			int j = i + size;
			
			//i~j 먹고, 왼쪽에 서있을때

			ll l = relu(candy - elapsed[i + 1][j][0] - abs(v[i+1] - v[i]));
			ll r = relu(candy - elapsed[i + 1][j][1] - abs(v[j] - v[i]));

			if (can[i + 1][j][0] + l < can[i + 1][j][1] + r) {
				elapsed[i][j][0] = elapsed[i + 1][j][1] + abs(v[j] - v[i]);
				can[i][j][0] = can[i + 1][j][1] + r;
			}
			else {
				elapsed[i][j][0] = elapsed[i + 1][j][0] + abs(v[i + 1] - v[i]);
				can[i][j][0] = can[i + 1][j][0] + l;
			}

			////////////////////////////////////////////////////////////////////

			//i~j 먹고 오른쪽에 서있을때

			
			l = relu(candy - elapsed[i][j - 1][0] - abs(v[i] - v[j]));
			r = relu(candy - elapsed[i][j - 1][1] - abs(v[j - 1] - v[j]));

			if (can[i][j - 1][0] + l < can[i][j - 1][1] + r) {
				elapsed[i][j][1] = elapsed[i][j - 1][1] + abs(v[j - 1] - v[j]);
				can[i][j][1] = can[i][j - 1][1] + r;
			}
			else {
				elapsed[i][j][1] = elapsed[i][j - 1][0] + abs(v[i] - v[j]);
				can[i][j][1] = can[i][j - 1][0] + l;

			}
		}
	}
	cout << max3(can[0][n - 1][0], can[0][n - 1][1],0);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4퍼 터지는 예외 ㅜ

rlarlvy153 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말