#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);
| ^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |