oj.uz

Submission #949839

# Submission time Handle Problem Language Result Execution time Memory
949839 2024-03-19T18:29:46 Z rainboy 전화번호 나누기 (KPI13_telephone) C
1 / 1
 928 ms 468 KB 
#include <stdio.h>
#include <string.h>

#define N	512
#define K	30
#define B	1000000000000000000
#define INF	0x3f3f3f3f3f3f3f3fLL

void 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_;
	}
}

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);
	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++) {
				concat(aa, cc[j] - '0');
				add(dp[i], aa, bb);
				chmin(dp[j + 1], bb);
			}
		}
	print(dp[n]);
	return 0;
}

Compilation message

telephone.c: In function 'main':
telephone.c:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 370 ms 348 KB Output is correct
11 Correct 928 ms 468 KB Output is correct
12 Correct 107 ms 348 KB Output is correct
13 Correct 13 ms 348 KB Output is correct