글 읽기 - 행님들 한번만 더 도와주세요

kaiose 6년 전 0

아까 djm03178 행님이 도와주셔서 sum 값 longlong으로 바꾸고 출력 lld로 해서 채점하기 시작하니까 기분좋았는데

시간초과나네요..

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <math.h>
#include <string.h>

int ctSort(int* arrT, int K, int d) {
	int* arr = new int[K];
	memcpy(arr, arrT, sizeof(int)*K);
	int degree = 10;
	int* temp = new int[K];
	memset(temp, 0, sizeof(int)*K);
	int result = 0;
	for (int p = 0; p < d; p++) {
		int count[10] = { 0 };
		int num = (int)pow(10, p);
		for (int i = 0; i < K; i++) { count[(arr[i] % (num * 10)) / num]++; }
		for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; }
		for (int i = K - 1; i >= 0; i--) {
			temp[count[(arr[i] % (num * 10)) / num] - 1] = arr[i];
			count[(arr[i] % (num * 10)) / num]--;
		}
		degree *= 10;
		for (int i = 0; i < K; i++) {
			arr[i] = temp[i];
		}
	}
	result = temp[(K + 1) / 2 - 1];
	delete[] arr;
	delete[] temp;
	return result;
}
int main() {
	int N; // 갯수
	int K; // 연속수갯수
	scanf("%d%d", &N, &K);
	long long sum = 0;
	int* temp = new int[K];
	memset(temp, 0, sizeof(int)*K);
	int max = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &temp[i%K]);
		if (max < temp[i%K]) { max = temp[i%K]; }
		int count = 0;
		
		while (true) {
			if (max / (int)pow(10, count) == 0) break;
			count++;
		}// 진법
		if (i >= K - 1) {
			sum += ctSort(temp, K, count); //카운트소팅
		}
	}
	printf("%lld", sum);
	delete[] temp;
	return 0;
}

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

문제

문제

출처

ICPC

행님들 한번만 더 도와주세요

kaiose 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말