| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 219290 |
2020-04-05T04:54:58 Z |
rama_pang |
Lamps (JOI19_lamps) |
C++14 |
|
1000 ms |
67012 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e7;
int N;
string A, B;
void Read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> A >> B;
}
int NaiveDP() {
vector<array<array<int, 4>, 4>> dp(N + 1); // dp[pos][second_last_operation][last_operation]
// dp[pos] means A[pos...N] = B[pos...N]
// operation 0 = skip operation, costs 0
// operation 1 = off operation, costs 1 if not (second_last == 1 and last == 2), otherwise costs 0 (but then new_second_last is considered operation 0, since we cannot cascade alternating 1 and 2)
// operation 2 = on operation, costs 1 if not (second_last == 2 and last == 1), otherwise costs 0 (but then new_second_last is considered operation 0, since we cannot cascade alternating 1 and 2)
// operation 3 = xor operation, costs 1 if not (second_last == 1 and last == 2 or vice versa), otherwise costs 0
for (int pos = N - 1; pos >= 0; pos--) {
for (int second_last = 0; second_last < 4; second_last++) {
for (int last = 0; last < 4; last++) {
int &res = dp[pos][second_last][last];
int is12 = second_last == 1 && last == 2;
int is21 = second_last == 2 && last == 1;
// operation skip (0)
if (A[pos] == B[pos]) {
res = dp[pos + 1][last][0];
} else {
res = INF;
}
// operation off (1)
for (int nxt = pos; nxt < N; nxt++) {
if (B[nxt] != '0') break;
res = min(res, 1 + dp[nxt + 1][last][1]);
res = min(res, 1 - is12 + dp[nxt + 1][0][1]);
}
// operation on (2)
for (int nxt = pos; nxt < N; nxt++) {
if (B[nxt] != '1') break;
res = min(res, 1 + dp[nxt + 1][last][2]);
res = min(res, 1 - is21 + dp[nxt + 1][0][2]);
}
// operation xor (3)
for (int nxt = pos; nxt < N; nxt++) {
if (A[nxt] == B[nxt]) break;
res = min(res, 1 - (is12 || is21) + dp[nxt + 1][last][3]);
}
}
}
}
return dp[0][0][0];
}
int main() {
Read();
cout << NaiveDP() << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Execution timed out |
1100 ms |
67012 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
