oj.uz

Submission #949835

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

#define N	256
#define K	15
#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);
	assert(n <= 200);
	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: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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Runtime error 1 ms 344 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -