| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1114337 |
2024-11-18T15:37:29 Z |
yellowtoad |
Lamps (JOI19_lamps) |
C++17 |
|
62 ms |
28876 KB |
#include <iostream>
using namespace std;
int n, dp[1000010][6]; // 4: 12, 5: 21;
string s, t;
int main() {
cin >> n >> s >> t;
for (int i = 0; i <= n; i++) for (int j = 0; j < 6; j++) dp[i][j] = 1e9;
dp[0][0] = 0;
s = " "+s; t = " "+t;
for (int i = 1; i <= n; i++) {
if (s[i] == t[i]) dp[i][0] = min(min(min(dp[i-1][0],dp[i-1][1]),min(dp[i-1][2],dp[i-1][3])),min(dp[i-1][4],dp[i-1][5]));
if (t[i] == '0') dp[i][1] = min(min(min(dp[i-1][0]+1,dp[i-1][1]),min(dp[i-1][2]+1,dp[i-1][3]+1)),min(dp[i-1][4],dp[i-1][5]+1));
if (t[i] == '1') dp[i][2] = min(min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2],dp[i-1][3]+1)),min(dp[i-1][4]+1,dp[i-1][5]));
if (s[i] != t[i]) dp[i][3] = min(min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2]+1,dp[i-1][3])),min(dp[i-1][4]+1,dp[i-1][5]+1));
if (t[i] == '1') dp[i][4] = min(min(min(dp[i-1][0]+2,dp[i-1][1]+1),min(dp[i-1][2]+2,dp[i-1][3]+2)),min(dp[i-1][4],dp[i-1][5]+2));
if (t[i] == '0') dp[i][5] = min(min(min(dp[i-1][0]+2,dp[i-1][1]+2),min(dp[i-1][2]+1,dp[i-1][3]+2)),min(dp[i-1][4]+2,dp[i-1][5]));
}
cout << min(min(min(dp[n][0],dp[n][1]),min(dp[n][2],dp[n][3])),min(dp[n][4],dp[n][5])) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
46 ms |
28844 KB |
Output is correct |
| 8 |
Correct |
45 ms |
28796 KB |
Output is correct |
| 9 |
Correct |
42 ms |
28796 KB |
Output is correct |
| 10 |
Correct |
41 ms |
28816 KB |
Output is correct |
| 11 |
Correct |
42 ms |
28776 KB |
Output is correct |
| 12 |
Correct |
45 ms |
28840 KB |
Output is correct |
| 13 |
Correct |
44 ms |
28776 KB |
Output is correct |
| 14 |
Correct |
62 ms |
28876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
