글 읽기 - 예제는 모두 맞는데 틀리다고 나오네요..ㅠㅠㅠ

illiboy1212 5년 전 0

어디가 잘못된 걸까요...ㅠㅠ 누적합에서 같은 색깔의 부분합을 빼는 방법으로 코딩해봤습니다ㅠ.ㅠ

#include<cstdio>
#include<algorithm>

using namespace std;

int sum[200100];

struct pp
{
	int colors;
	int size;
	int num;
};

bool cmp(pp a, pp b)
{
	return a.size < b.size;
}
pp arr[200100];

int col[200100];
int a;

int main()
{
	scanf("%d", &a);
	for (int i = 1; i<= a; i++)
	{
		scanf("%d %d", &arr[i].colors, &arr[i].size);
		arr[i].num=i;
	}

	sort(arr+1, arr+a+1, cmp);

	int snu = 0;

	for (int i = 1; i <= a; i++)
	{
		snu+=arr[i-1].size;
		sum[arr[i].num]= snu - col[arr[i].colors];
		col[arr[i].colors]+=arr[i].size;
	}
	for (int i = 1; i <= a; i++)
	{
		printf("%d\n", sum[i]);
	}
}

//https://www.acmicpc.net/problem/10800 

oree2113 5년 전 0

이 코드에서는 크기가 같은 다른 색 공이 잡아먹을 수 있는걸로 보입니다.

1 10

2 10

결과 확인해주세요

illiboy1212 5년 전 0

아래와 같이 수정해서 중복된 크기를 먹는 문제를 해결하였는데, 또 틀렸다고 나오네요..ㅠㅠ

#include<cstdio>
#include<algorithm>

using namespace std;

int sum[200100];

struct pp
{
	int colors;
	int size;
	int num;
};

bool cmp(pp a, pp b)
{
	return a.size < b.size;
}
pp arr[200100];

int col[200100];
int siz[2010];
int a;

int main()
{
	scanf("%d", &a);
	for (int i = 1; i<= a; i++)
	{
		scanf("%d %d", &arr[i].colors, &arr[i].size);
		arr[i].num=i;
	}

	sort(arr+1, arr+a+1, cmp);

	int snu = 0;

	for (int i = 1; i <= a; i++)
	{
		snu+=arr[i-1].size;
		sum[arr[i].num]= snu - col[arr[i].colors] - siz[arr[i].size]*arr[i].size;
		siz[arr[i].size]++;
		col[arr[i].colors]+=arr[i].size;
	}
	for (int i = 1; i <= a; i++)
	{
		printf("%d\n", sum[i]);
	}
}

//https://www.acmicpc.net/problem/10800 

leekasong 3년 전 4

이거 아마 같은 색깔, 같은 숫자인 케이스에 대해서 처리 못하는 것 같아요

반례)

10
1 10
1 10
2 10
3 10
1 9
1 8
1 7
2 3
3 1
3 1

답)

5
5
26
27
5
5
5
2
0
0

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

문제

문제

출처

ICPC

예제는 모두 맞는데 틀리다고 나오네요..ㅠㅠㅠ

illiboy1212 5년 전 0

oree2113 5년 전 0

illiboy1212 5년 전 0

leekasong 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말