CSES - KILO 2018 2/5

Submission details
Task:	Fused Folder
Sender:	ollpu_kilo
Submission time:	2018-09-13 18:57:32 +0300
Language:	C++
Status:	READY
Result:	TIME LIMIT EXCEEDED

Test results
test	verdict	time
#1	ACCEPTED	0.01 s	details
#2	ACCEPTED	0.01 s	details
#3	ACCEPTED	0.01 s	details
#4	ACCEPTED	0.03 s	details
#5	ACCEPTED	0.02 s	details
#6	ACCEPTED	0.01 s	details
#7	ACCEPTED	0.02 s	details
#8	ACCEPTED	0.02 s	details
#9	ACCEPTED	0.01 s	details
#10	ACCEPTED	0.01 s	details
#11	ACCEPTED	1.29 s	details
#12	ACCEPTED	1.21 s	details
#13	ACCEPTED	0.06 s	details
#14	ACCEPTED	0.37 s	details
#15	ACCEPTED	0.53 s	details
#16	TIME LIMIT EXCEEDED	--	details
#17	TIME LIMIT EXCEEDED	--	details
#18	TIME LIMIT EXCEEDED	--	details
#19	TIME LIMIT EXCEEDED	--	details
#20	TIME LIMIT EXCEEDED	--	details
#21	TIME LIMIT EXCEEDED	--	details
#22	TIME LIMIT EXCEEDED	--	details
#23	TIME LIMIT EXCEEDED	--	details
#24	TIME LIMIT EXCEEDED	--	details
#25	TIME LIMIT EXCEEDED	--	details
#26	TIME LIMIT EXCEEDED	--	details
#27	TIME LIMIT EXCEEDED	--	details
#28	TIME LIMIT EXCEEDED	--	details
#29	ACCEPTED	0.67 s	details
#30	ACCEPTED	0.67 s	details
#31	TIME LIMIT EXCEEDED	--	details
#32	TIME LIMIT EXCEEDED	--	details
#33	ACCEPTED	1.38 s	details

Code

#pragma GCC optimize ("O3")
#pragma GCC target ("arch=skylake")
#include <bits/stdc++.h>
using namespace std;
int dp[2][25001];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int A, B, F;
  cin >> A >> B >> F;
  string a, b, f;
  cin >> a >> b >> f;
  for (int i = 0; i <= A; ++i) {
    int ci = i&1, li = ~i&1;
    for (int j = 0; j <= B; ++j) {
      if (i == 0 && j == 0) {
        dp[ci][j] = 0;
        continue;
      }
      int res = F+1;
      if (i && dp[li][j] < F) {
        res = min(res, dp[li][j]+(f[dp[li][j]] == a[i-1]));
      }
      if (j && dp[ci][j-1] < F) {
        res = min(res, dp[ci][j-1]+(f[dp[ci][j-1]] == b[j-1]));
      }
      if (i && j && a[i-1] == b[j-1] && dp[li][j-1] < F) {
        res = min(res, dp[li][j-1]+(f[dp[li][j-1]] == a[i-1]));
      }
      dp[ci][j] = res;
    }
  }
  cout << (dp[A&1][B] < F ? "YES" : "NO") << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`6 6 6 abbacc bacbac bbaacc` view save

correct output
`YES` view save

user output
`YES` view save

Test 2

Verdict: ACCEPTED

input
`3 3 2 aab aba ab` view save

correct output
`NO` view save

user output
`NO` view save

Test 3

Verdict: ACCEPTED

input
`2 1 1 nf l n` view save

correct output
`NO` view save

user output
`NO` view save

Test 4

Verdict: ACCEPTED

input
`8 2 3 fjnclbff lg dcc` view save

correct output
`YES` view save

user output
`YES` view save

Test 5

Verdict: ACCEPTED

input
`3 3 8 cca bvs iabhqblp` view save

correct output
`YES` view save

user output
`YES` view save

Test 6

Verdict: ACCEPTED

input
`5 7 4 fnefw frbujda sdsy` view save

correct output
`YES` view save

user output
`YES` view save

Test 7

Verdict: ACCEPTED

input
`10 10 4 aaaaaabbab aabababbaa babb` view save

correct output
`NO` view save

user output
`NO` view save

Test 8

Verdict: ACCEPTED

input
`6 7 1 fefgaa ddbebbb f` view save

correct output
`NO` view save

user output
`NO` view save

Test 9

Verdict: ACCEPTED

input
`10 3 1 afeglbeobc onj e` view save

correct output
`NO` view save

user output
`NO` view save

Test 10

Verdict: ACCEPTED

input
`3 6 3 aab abbaab aaa` view save

correct output
`NO` view save

user output
`NO` view save

Test 11

Verdict: ACCEPTED

input
`17639 10996 8710 idokahghjkldghkkiegdaopealioon...` view save

correct output
`YES` view save

user output
`YES` view save

Test 12

Verdict: ACCEPTED

input
`13616 19964 101 fffbfcffccabfeddddcfcbfcaeeedf...` view save

correct output
`NO` view save

user output
`NO` view save

Test 13

Verdict: ACCEPTED

input
`574 9006 730 jjbfvgcqlffbmsfaabnsstutmnvvsn...` view save

correct output
`YES` view save

user output
`YES` view save

Test 14

Verdict: ACCEPTED

input
`14601 4082 918 edjekbfklgklbcldkefecckifgifab...` view save

correct output
`NO` view save

user output
`NO` view save

Test 15

Verdict: ACCEPTED

input
`20842 3618 22126 cefagfddfecafccgdfbbafgadcdaab...` view save

correct output
`YES` view save

user output
`YES` view save

Test 16

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 19987 bbaaaababbaabbbabbabbaabaaabba...` view save

correct output
`YES` view save

user output
(empty)

Test 17

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 2654 aacbdadeacbcdccddedcdeecdaaecd...` view save

correct output
`NO` view save

user output
(empty)

Test 18

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 21163 baabbabbaaaaabaabbabbbbbababaa...` view save

correct output
`YES` view save

user output
(empty)

Test 19

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 807 iihklfjfdljejeeigibgkachiijkkd...` view save

correct output
`NO` view save

user output
(empty)

Test 20

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 14673 nwmhuqbldgvcdmsjjnsvmsoabwhvch...` view save

correct output
`YES` view save

user output
(empty)

Test 21

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 abbacbbaabacccbbccabbcccabaacc...` view save

correct output
`YES` view save

user output
(empty)

Test 22

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 ebgcfecbbeabhdhcdcidcebiiccacb...` view save

correct output
`YES` view save

user output
(empty)

Test 23

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 jhcdfcjeicfaagagaidijihaghhhjd...` view save

correct output
`YES` view save

user output
(empty)

Test 24

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 bqrehnjncmasbsesfoonmqlojickqh...` view save

correct output
`NO` view save

user output
(empty)

Test 25

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 cdfafbafcddafabdddbabdcbafbfec...` view save

correct output
`NO` view save

user output
(empty)

Test 26

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 wmuwshejgvqtiqrhbewlulksnskqjf...` view save

correct output
`NO` view save

user output
(empty)

Test 27

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 25000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...` view save

correct output
`NO` view save

user output
(empty)

Test 28

Verdict: TIME LIMIT EXCEEDED

input
`24999 24999 25000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...` view save

correct output
`YES` view save

user output
(empty)

Test 29

Verdict: ACCEPTED

input
`10000 10000 10000 cjscerkmfabqallhbibbhlaihfckpc...` view save

correct output
`NO` view save

user output
`NO` view save

Test 30

Verdict: ACCEPTED

input
`10000 10000 10000 fodgaeiqjbocpodglembnamebdimqb...` view save

correct output
`NO` view save

user output
`NO` view save

Test 31

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 12500 isaqmrnhixucovgtmcanojpdjnrops...` view save

correct output
`NO` view save

user output
(empty)

Test 32

Verdict: TIME LIMIT EXCEEDED

input
`25000 25000 12500 aofhfsqifcrdezfmzoakkpfdwodcfh...` view save

correct output
`NO` view save

user output
(empty)

Test 33

Verdict: ACCEPTED

input
`25000 8333 12500 qoromlkxbskfhvcubtrnyztgieeykk...` view save

correct output
`YES` view save

user output
`YES` view save

KILO 2018 2/5

Fused Folder

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Tasks

Submissions (ollpu_kilo)