Submission #61179170
Source Code Expand
Copy
#include <iostream>#include <string>#include <algorithm>using namespace std;int main() {int K;string S, T;cin >> K >> S >> T;int lenS = S.size();int lenT = T.size();const int INF = K + 1;int dp[2][1005];for (int j = 0; j <= lenT; ++j) {dp[0][j] = j <= K ? j : INF;}for (int i = 1; i <= lenS; ++i) {
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { int K; string S, T; cin >> K >> S >> T; int lenS = S.size(); int lenT = T.size(); const int INF = K + 1; int dp[2][1005]; for (int j = 0; j <= lenT; ++j) { dp[0][j] = j <= K ? j : INF; } for (int i = 1; i <= lenS; ++i) { int current = i % 2; int prev = 1 - current; dp[current][0] = i <= K ? i : INF; for (int j = 1; j <= lenT; ++j) { dp[current][j] = INF; dp[current][j] = min(dp[current][j], dp[prev][j] + 1); dp[current][j] = min(dp[current][j], dp[current][j - 1] + 1); dp[current][j] = min(dp[current][j], dp[prev][j - 1] + (S[i - 1] == T[j - 1] ? 0 : 1)); if (dp[current][j] > K) { dp[current][j] = INF; } } bool allExceed = true; for (int j = 0; j <= lenT; ++j) { if (dp[current][j] <= K) { allExceed = false; break; } } if (allExceed) { cout << "No" << endl; return 0; } } if (dp[lenS % 2][lenT] <= K) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Operate K |
User | Untitle |
Language | C++ 23 (gcc 12.2) |
Score | 0 |
Code Size | 1412 Byte |
Status | RE |
Exec Time | 97 ms |
Memory | 5336 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 525 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt, small_05.txt, small_06.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hand_01.txt | RE | 91 ms | 5184 KB |
hand_02.txt | RE | 90 ms | 5100 KB |
hand_03.txt | RE | 92 ms | 5268 KB |
hand_04.txt | RE | 91 ms | 5180 KB |
sample_01.txt | AC | 1 ms | 3572 KB |
sample_02.txt | AC | 1 ms | 3456 KB |
sample_03.txt | AC | 1 ms | 3504 KB |
small_01.txt | AC | 1 ms | 3448 KB |
small_02.txt | AC | 1 ms | 3476 KB |
small_03.txt | AC | 1 ms | 3504 KB |
small_04.txt | AC | 1 ms | 3500 KB |
small_05.txt | AC | 1 ms | 3664 KB |
small_06.txt | AC | 1 ms | 3576 KB |
test_01.txt | AC | 1 ms | 3476 KB |
test_02.txt | AC | 1 ms | 3504 KB |
test_03.txt | AC | 1 ms | 3372 KB |
test_04.txt | AC | 1 ms | 3456 KB |
test_05.txt | AC | 1 ms | 3476 KB |
test_06.txt | RE | 91 ms | 5172 KB |
test_07.txt | RE | 91 ms | 5216 KB |
test_08.txt | RE | 91 ms | 5188 KB |
test_09.txt | RE | 90 ms | 5204 KB |
test_10.txt | RE | 90 ms | 5200 KB |
test_11.txt | RE | 84 ms | 4156 KB |
test_12.txt | AC | 7 ms | 4064 KB |
test_13.txt | RE | 80 ms | 3540 KB |
test_14.txt | RE | 80 ms | 3788 KB |
test_15.txt | RE | 92 ms | 5336 KB |
test_16.txt | RE | 92 ms | 5188 KB |
test_17.txt | RE | 91 ms | 5332 KB |
test_18.txt | RE | 92 ms | 5184 KB |
test_19.txt | RE | 90 ms | 5184 KB |
test_20.txt | RE | 90 ms | 5196 KB |
test_21.txt | RE | 93 ms | 5332 KB |
test_22.txt | RE | 91 ms | 5204 KB |
test_23.txt | RE | 91 ms | 5252 KB |
test_24.txt | RE | 93 ms | 5076 KB |
test_25.txt | RE | 93 ms | 5252 KB |
test_26.txt | RE | 93 ms | 5224 KB |
test_27.txt | RE | 93 ms | 5256 KB |
test_28.txt | RE | 93 ms | 5204 KB |
test_29.txt | RE | 92 ms | 5200 KB |
test_30.txt | RE | 94 ms | 5172 KB |
test_31.txt | RE | 89 ms | 4140 KB |
test_32.txt | AC | 7 ms | 4140 KB |
test_33.txt | RE | 94 ms | 5336 KB |
test_34.txt | RE | 88 ms | 3904 KB |
test_35.txt | RE | 92 ms | 4204 KB |
test_36.txt | RE | 96 ms | 5208 KB |
test_37.txt | RE | 97 ms | 5196 KB |
test_38.txt | RE | 96 ms | 5176 KB |
test_39.txt | RE | 94 ms | 5172 KB |
test_40.txt | RE | 97 ms | 5104 KB |
test_41.txt | RE | 96 ms | 5128 KB |
test_42.txt | RE | 95 ms | 5336 KB |
test_43.txt | RE | 96 ms | 5236 KB |
test_44.txt | RE | 93 ms | 5180 KB |
test_45.txt | RE | 93 ms | 5180 KB |
test_46.txt | RE | 93 ms | 5332 KB |
test_47.txt | RE | 93 ms | 5180 KB |
test_48.txt | RE | 94 ms | 4964 KB |
test_49.txt | RE | 95 ms | 4836 KB |
test_50.txt | RE | 93 ms | 4924 KB |
test_51.txt | RE | 94 ms | 4920 KB |
test_52.txt | RE | 93 ms | 4912 KB |
test_53.txt | RE | 95 ms | 4960 KB |
test_54.txt | RE | 93 ms | 4916 KB |
test_55.txt | RE | 96 ms | 5008 KB |
test_56.txt | RE | 96 ms | 4928 KB |
test_57.txt | RE | 94 ms | 4928 KB |
test_58.txt | RE | 95 ms | 4912 KB |
test_59.txt | RE | 92 ms | 4832 KB |
test_60.txt | RE | 91 ms | 4932 KB |
test_61.txt | RE | 90 ms | 4924 KB |
test_62.txt | RE | 93 ms | 4936 KB |
test_63.txt | RE | 90 ms | 4980 KB |
test_64.txt | AC | 1 ms | 3504 KB |
test_65.txt | AC | 1 ms | 3508 KB |
test_66.txt | AC | 1 ms | 3468 KB |
test_67.txt | AC | 1 ms | 3576 KB |
test_68.txt | AC | 1 ms | 3508 KB |
test_69.txt | AC | 1 ms | 3440 KB |
test_70.txt | AC | 1 ms | 3424 KB |