10800번 - 컬러볼

C++17

#include <bits/stdc++.h>

using namespace std;

#define Max 200002

int n, sum, color[Max], clm[Max / 100 + Max % 10];
vector<pair<int, int> > v;
vector<int> same_color[Max];

bool cmp(const int & a, const int & b)
{
	return a > b;
}

int same(int c, int s)
{
	int ret = 0;

	for (auto i : same_color[c]) {
		if (i < s) {
			break;
		}
		ret += i;
	}

	return ret;
}

int main()
{
	cin.tie(0);
	scanf("%d", &n);

	int c, s, max_size = 0, max_color = 0;

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &c, &s);
		v.push_back({ s, c }); // { 크기, 색깔 }
		sum += s; // 크기의 총 합
		color[c] += s; // color[c] : c 색의 크기(s)의 총합
		clm[s] += s; // clm[s] : s 크기에 해당하는 크기(s)의 총합
		max_size = max(max_size, s); // 변수 활용해야함. 크기(s)의 최댓값.
		same_color[c].push_back(s); // 같은 색깔(c)에 해당하는 s의 집합
		max_color = max(max_color, c);
	}

	// 누적합 : cumulative sum (clm)
	for (int i = 1; i <= max_size; i++) {
		clm[i] += clm[i - 1];
	}

	// 같은 색깔이면서 자신의 크기보다 큰 크기들의 누적 크기 합
	for (int i = 1; i <= max_color; i++) {
		if (!same_color[i].empty()) {
			sort(same_color[i].begin(), same_color[i].end(), cmp);
		}
	}

	for (auto i : v) {
		// 답 : 총 크기의 합 - (같은 색깔에 해당하는 크기의 합 + 자신의 크기(s)보다 같거나 큰 크기들의 누적 크기 합)
		int answer = sum - (color[i.second] + clm[max_size] - clm[i.first - 1]);
		// 20 - (color[1]=10 + clm[2]=10 - clm[1]=10)
		answer += same(i.second, i.first);
		printf("%d\n", answer);
	}
	
	return 0;
}

결과	메모리	시간	코드 길이
시간 초과			1620

문제

문제

출처

ICPC

C++17

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말