글 읽기 - 반례도 다 맞는데 9퍼센트에서 틀립니다

sm1108shin 2년 전 1

모든 반례들 다 넣어봤는데 다 되는데 왜 틀렸다고 뜰까요..

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <limits.h>
#include <string>
#include <cstdlib>
using namespace std;

vector<tuple<int, int, int>> event;
int Min = 100000001;
int ans[1001];
int dp[1001][1001];

void dfs(int n, int w, int i, int j, int k, int* bx1, int* by1, int* bx2, int* by2)
{

	if (k == w)
	{
		if (Min > dp[i][j])
		{
			Min = dp[i][j];
			for (int i = 0; i < w; i++)
			{
				ans[i] = get<2>(event[i]);
			}
		}
		*bx1 = 1, * by1 = 1, * bx2 = n, * by2 = n;
		return;
	}

	if (dp[i][j] > Min)
	{
		return;
	}

	int x = get<0>(event[k]);
	int y = get<1>(event[k]);

	int plus = abs(x - *bx1) + abs(y - *by1);

	if (!dp[i + 1][j] || dp[i + 1][j] > dp[i][j] + plus)
	{
		*bx1 = x, *by1 = y;
		dp[i + 1][j] = dp[i][j] + plus;
		get<2>(event[k]) = 1;
		dfs(n, w, i + 1, j, k + 1, bx1, by1, bx2, by2);
	}

	int plus2 = abs(x - *bx2) + abs(y - *by2);
	
	if(!dp[i][j+1] || dp[i][j+1] > dp[i][j] + plus2)
	{
		*bx2 = x, *by2 = y;
		dp[i][j + 1] = dp[i][j] + plus2;
		get<2>(event[k]) = 2;
		dfs(n, w, i, j + 1, k + 1, bx1, by1, bx2, by2);
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, w;
	cin >> n;
	cin >> w;

	dp[0][0] = 0;

	int bx1 = 1, by1 = 1;
	int bx2 = n, by2 = n;

	for (int i = 0; i < w; i++)
	{
		int a, b;
		cin >> a >> b;
		event.emplace_back(make_tuple(a, b, 0));
	}

	dfs(n, w, 0, 0, 0, &bx1, &by1, &bx2, &by2);

	//for (int i = 0; i <= w; i++)
	//{
	//	for (int j = 0; j <= w; j++)
	//	{
	//		cout << dp[i][j] << " ";
	//	}
	//	cout << '\n';
	//}

	cout << Min << "\n";

	for (int i = 0; i < w; i++)
	{
		cout << ans[i] << '\n';
	}
}

vmffotltka 1년 전 2

반례입니다.

input:

1000

1 1000

1000 1

1 1000

1000 1

1 1000

answer:

1998

20wjsdudtj 1년 전 0

이거 데이터 반영이 안 되어서 그런 거인 것 같아요ㅠㅠ 저도 9퍼에서 계속 틀렸습니다..ㅠㅠ 그래서 데이터 추가 요청했습니다!!

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

문제

문제

출처

ICPC

반례도 다 맞는데 9퍼센트에서 틀립니다

sm1108shin 2년 전 1

vmffotltka 1년 전 2

20wjsdudtj 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말