Submission #3773008
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int K = 10005;
int n, k;
char s[N][K];
int len[N];
bitset<K> dp[N];
int nv, tnv;
pair<int, int> v[2][K];
int main() {
scanf("%d %d",&n,&k);
for (int i = 1; i <= n; i++) {
scanf("%s", s[i]);
len[i] = strlen(s[i]);
}
dp[n + 1][0] = 1;
for (int i = n; i > 0; i--) {
dp[i] = dp[i + 1] | (dp[i + 1] << len[i]);
}
for (int i = 1; i <= n; i++) {
if (dp[i + 1][k - len[i]]) {
v[0][nv++]= make_pair(i, 0);
}
}
for (int iter = 1,i = 1; iter <= k; iter++, i ^= 1) {
tnv = 0;
char c = 'z';
for (int j = 0; j < nv; j++) {
c = min(c, s[v[i ^ 1][j].first][v[i ^ 1][j].second]);
}
putchar(c);
int bid = n + 1;
for (int j = 0; j < nv; j++) {
int id = v[i ^ 1][j].first;
int pos = v[i ^ 1][j].second;
if (s[id][pos] != c) {
continue;
}
if (pos < len[id] - 1)
v[i][tnv++] = make_pair(id, pos+1);
else {
bid = min(bid, id);
}
}
for (int j = bid + 1; j <= n; j++) {
if (k - iter - len[j] >= 0 && dp[j + 1][k - iter - len[j]]) {
v[i][tnv++] = make_pair(j, 0);
}
}
nv = tnv;
}
putchar('\n');
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Iroha Loves Strings |
User |
nthoang |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1300 Byte |
Status |
WA |
Exec Time |
328 ms |
Memory |
21504 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:16:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&k);
^
./Main.cpp:18:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_sample01, 0_sample02, 0_sample03 |
All |
0_sample01, 0_sample02, 0_sample03, abab0, abten0, allsame0, allsame_ex0, bigrand0, bigrand1, firstlast0, firstlast1, fullrand0, fullrand1, fullrand2, kaidan0, maxrand0, maxrand1, maxrand2, roll_hyper0, roll_hyper1, roll_hyper_r0, rolling0, rolling1, smallc0, smallc1, smallrand0, smallrand1, smallrand2, zzza0 |
Case Name |
Status |
Exec Time |
Memory |
0_sample01 |
AC |
2 ms |
2304 KB |
0_sample02 |
AC |
2 ms |
2304 KB |
0_sample03 |
AC |
2 ms |
2304 KB |
abab0 |
WA |
133 ms |
18688 KB |
abten0 |
AC |
8 ms |
21376 KB |
allsame0 |
WA |
209 ms |
21504 KB |
allsame_ex0 |
WA |
328 ms |
21376 KB |
bigrand0 |
AC |
6 ms |
16256 KB |
bigrand1 |
AC |
8 ms |
20608 KB |
firstlast0 |
AC |
8 ms |
21376 KB |
firstlast1 |
AC |
8 ms |
21376 KB |
fullrand0 |
AC |
8 ms |
21376 KB |
fullrand1 |
AC |
9 ms |
21376 KB |
fullrand2 |
AC |
8 ms |
21376 KB |
kaidan0 |
WA |
228 ms |
21504 KB |
maxrand0 |
AC |
8 ms |
21376 KB |
maxrand1 |
AC |
8 ms |
21376 KB |
maxrand2 |
AC |
8 ms |
21376 KB |
roll_hyper0 |
AC |
10 ms |
21376 KB |
roll_hyper1 |
AC |
10 ms |
21376 KB |
roll_hyper_r0 |
AC |
10 ms |
21376 KB |
rolling0 |
AC |
10 ms |
21376 KB |
rolling1 |
AC |
10 ms |
21376 KB |
smallc0 |
WA |
9 ms |
21376 KB |
smallc1 |
WA |
9 ms |
21376 KB |
smallrand0 |
AC |
2 ms |
2304 KB |
smallrand1 |
AC |
2 ms |
2304 KB |
smallrand2 |
AC |
2 ms |
2304 KB |
zzza0 |
AC |
8 ms |
20736 KB |