글 읽기 - 2515번 반례부탁드립니다. ㅠㅠ

hyj5419 4년 전 0

어느부분이 빠진건지 모르겠습니다. ㅠㅠ 반례부탁드립니다!

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
#include<string>
#include<climits>
#include<string.h>

using namespace std; 
pair<long long int, long long int> p[300005];
long long int cost[300005][4];
long long int len[300005][4];
int main() {
	long long int n, s;
	scanf("%lld%lld", &n, &s);
	for (long long int i = 0; i < n; i++) {
		long long int a, b;
		scanf("%lld%lld", &a, &b);
		p[i].first = a;//length
		p[i].second = b;//cost
	}
	sort(p, p + n);
	cost[0][0] = 0;
	cost[0][1] = p[0].second;
	len[0][1] = p[0].first;

	for (long long int i = 1; i < n; i++) {
		long long int nl = p[i].first;
		long long int nc = p[i].second;
		if (nl - len[i-1][0] >= s&&nl - len[i-1][1] >= s) {
			cost[i][0] = max(cost[i - 1][0], cost[i - 1][1]);
			cost[i][1]= max(cost[i - 1][0],cost[i-1][1])+nc;
			if (cost[i - 1][0] > cost[i - 1][1]) {
				len[i][0] = len[i - 1][0];
			}
			else {
				len[i][0] = len[i - 1][1];
			}
			len[i][1] = nl;
		}
		else if (nl - len[i-1][0] >= s&&nl - len[i-1][1] < s) {
			cost[i][1] = cost[i - 1][0]+nc;
			cost[i][0] = max(cost[i - 1][0], cost[i - 1][1]);
			len[i][1] = nl;
			if (cost[i - 1][0] > cost[i - 1][1]) {
				len[i][0] = len[i - 1][0];
			}
			else {
				len[i][0] = len[i - 1][1];
			}
		}
		else {
			cost[i][1] = max(cost[i - 1][1],nc);
			cost[i][0] = max(cost[i - 1][0],cost[i-1][1]);
			len[i][0] = len[i - 1][0];
			len[i][1] = len[i - 1][1];
		}
	}
	/*for (long long int i = 0; i < n; i++) {
		printf("%d %d\n", cost[i][0], cost[i][1]);
	}
	cout << "----" << endl;
	for (long long int i = 0; i < n; i++) {
		printf("%d %d\n", len[i][0], len[i][1]);
	}*/
	printf("%lld\n", max(cost[n-1][0], cost[n-1][1]));
}

hgc950909 4년 전 0

해결했어요.

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

문제

문제

출처

ICPC

2515번 반례부탁드립니다. ㅠㅠ

hyj5419 4년 전 0

hgc950909 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말