oj.uz

Submission #949845

# Submission time Handle Problem Language Result Execution time Memory
949845 2024-03-19T18:43:28 Z rainboy 전화번호 나누기 (KPI13_telephone) C
1 / 1
 243 ms 428 KB 
#include <stdio.h>
#include <string.h>

#define N	300
#define K	9
#define B	1000000000000000000
#define INF	0x3f3f3f3f3f3f3f3fLL

int concat(long long *aa, int d) {
	int h, d_;

	for (h = 0; h < K; h++) {
		d_ = aa[h] / (B / 10);
		aa[h] = aa[h] % (B / 10) * 10 + d;
		d = d_;
	}
	return d == 0;
}

void add(long long *aa, long long *bb, long long *cc) {
	int h;

	for (h = 0; h < K; h++)
		cc[h] = aa[h] + bb[h];
	for (h = 0; h + 1 < K; h++)
		if (cc[h] >= B)
			cc[h] -= B, cc[h + 1]++;
}

void chmin(long long *aa, long long *bb) {
	int h;

	for (h = K - 1; h >= 0; h--)
		if (aa[h] != bb[h]) {
			if (aa[h] > bb[h])
				memcpy(aa, bb, K * sizeof *bb);
			return;
		}
}

void print(long long *aa) {
	int h;

	h = K - 1;
	while (h > 0 && aa[h] == 0)
		h--;
	printf("%lld", aa[h]);
	while (h--)
		printf("%018lld", aa[h]);
	printf("\n");
}

int main() {
	static char cc[N + 1];
	static long long dp[N + 1][K], aa[K], bb[K];
	int n, k, i, j;

	scanf("%s%d", cc, &k), n = strlen(cc);
	if (k == 1) {
		i = 0;
		while (i + 1 < n && cc[i] == '0')
			i++;
		printf("%s\n", cc + i);
		return 0;
	}
	for (i = 1; i <= n; i++)
		memset(dp[i], 0x3f, K * sizeof *dp[i]);
	while (k--)
		for (i = n - 1; i >= 0; i--) {
			if (dp[i][0] == INF)
				continue;
			memset(aa, 0, K * sizeof *aa);
			for (j = i; j < n; j++) {
				if (!concat(aa, cc[j] - '0'))
					break;
				add(dp[i], aa, bb);
				chmin(dp[j + 1], bb);
			}
		}
	print(dp[n]);
	return 0;
}

Compilation message

telephone.c: In function 'main':
telephone.c:58:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%s%d", cc, &k), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 104 ms 348 KB Output is correct
11 Correct 243 ms 412 KB Output is correct
12 Correct 30 ms 348 KB Output is correct
13 Correct 4 ms 344 KB Output is correct