글 읽기 - 반례 좀 찾아주세요

jungeun38 5년 전 0

테스트 케이스랑

0 0

0 5

1 5

1 3

2 3

2 4

3 4

3 0

0 5 1 5

출력 : 1

0 0

0 3

1 3

1 4

2 4

2 3

3 3

3 0

1 4 2 4

출력 : 0

은 잘되는데 나머지 반례를 못찾겠습니다ㅜ

#include<stdio.h>
#include<vector>
#define MAX_N 5001
using namespace std;
int N, K;

int main() {
	int a, b, c, d;

	vector<int> v;
	//수족관 정보
	scanf("%d", &N);

	scanf("%d %d", &a, &b);
	for (int i = 0; i < (N - 2) / 2; ++i) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		for (int j = a; j < c; ++j)
			v.push_back(b);
	}
	scanf("%d %d", &a, &b);

	vector<int> hall;
	hall.assign(v.size(), 0);
	scanf("%d", &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		hall[a] = b;
	}

	vector<int> last;
	last.assign(v.size(), 0);

	int water = 0, sz = v.size();
	for (int i = 0; i < sz; ++i) {
		if (hall[i] == 0)
			continue;

		int h = hall[i];
		last[i] = h;
		//왼쪽
		for (int j = i - 1; j >= 0; --j) {
			if ((i - 1 >= 0) && (v[j] == hall[i - 1]))
				break;
			if (h > v[j])	h = v[j];
			if (last[j] <= h)	last[j] = h;
		}
		
		//오른쪽
		for (int j = i + 1; j < sz; ++j) {
			if((i + 1 < hall.size()) && (v[j] == hall[i + 1]))
				break;
			if (h > v[j])	h = v[j];
			if (last[j] <= h)	last[j] = h;
		}
	}

	for (int i = 0; i < sz; ++i)
		water += (v[i] - last[i]);

	printf("%d", water);
	return 0;
}

yu01203 4년 전 4

16
0 0
0 8
1 8
1 7
3 7
3 11
5 11
5 9
7 9
7 10
9 10
9 8
11 8
11 7
15 7
15 0
2
11 7 15 7
3 11 5 11

전 이렇게 구멍이 순차적으로 정렬 안되어 있으니 오류 나던거 정렬 해주니 되더라구요.

답은 3.

loveisasong17 4달 전 0

와..... 내 한 시간 ㅜㅜ

그래도 덕분에 한 시간으로 그쳤네요 ㅋㅋ

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

문제

문제

출처

ICPC

반례 좀 찾아주세요

jungeun38 5년 전 0

yu01203 4년 전 4

loveisasong17 4달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말