oj.uz

Submission #965019

# Submission time Handle Problem Language Result Execution time Memory
965019 2024-04-18T03:11:51 Z abczz Lamps (JOI19_lamps) C++14
4 / 100
 428 ms 98532 KB 
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

ll n, f = 1e18, dp[1000000][12];
string S, T;

ll get(ll u, vector <ll> state) {
  ll mn = 1e18;
  for (auto v : state) mn = min(mn, dp[u][v]);
  return mn;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> S >> T;
  for (int i=0; i<n; ++i) {
    for (int j=0; j<12; ++j) dp[i][j] = 1e18;
    if (S[i] != T[i]) {
      if (!i) dp[i][2] = 1;
      else dp[i][2] = min(get(i-1, {2, 3, 4, 5, 6, 7, 8}), get(i-1, {0, 1, 9, 10, 11})+1);
    }
    else {
      if (!i) dp[i][9] = 0;
      else {
        for (int j=0; j<12; ++j) {
          dp[i][9] = min(dp[i][9], dp[i-1][j]);
        }
      }
    }
    if (T[i] == '0') {
      if (!i) dp[i][0] = 1, dp[i][4] = dp[i][5] = dp[i][11] = 2, dp[i][8] = 3;
      else {
        dp[i][0] = min(get(i-1, {0, 3, 5, 7, 8, 10, 11}), get(i-1, {1, 2, 4, 6, 9})+1);
        dp[i][4] = min(get(i-1, {4}), min(get(i-1, {1, 2, 3, 5, 6, 7, 8, 10, 11})+1, get(i-1, {0, 9})+2));
        dp[i][5] = min(get(i-1, {5, 7, 8}), min(get(i-1, {0, 2, 3, 4, 6, 10, 11})+1, get(i-1, {1, 9})+2));
        dp[i][8] = min(get(i-1, {8, 11}), min(get(i-1, {5, 6, 7, 10})+1, min(get(i-1, {0, 1, 2, 3, 4})+2, get(i-1, {9})+3)));
        dp[i][11] = min(get(i-1, {8, 11}), min(get(i-1, {0, 1, 3, 4, 5, 6, 7, 10})+1, get(i-1, {2, 9})+2));
      }
    }
    else {
      if (!i) dp[i][1] = 1, dp[i][3] = dp[i][6] = dp[i][10] = 2, dp[i][7] = 3;
      else {
        dp[i][1] = min(get(i-1, {1, 4, 6, 7, 8, 10, 11}), get(i-1, {0, 2, 3, 5, 9})+1);
        dp[i][3] = min(get(i-1, {3}), min(get(i-1, {0, 2, 4, 5, 6, 7, 8, 10, 11})+1, get(i-1, {1, 9})+2));
        dp[i][6] = min(get(i-1, {6, 7, 8}), min(get(i-1, {1, 2, 3, 4, 5, 10, 11})+1, get(i-1, {0, 9}))+2);
        dp[i][7] = min(get(i-1, {7, 10}), min(get(i-1, {5, 6, 8, 11})+1, min(get(i-1, {0, 1, 2, 3, 4})+2, get(i-1, {9})+3)));
        dp[i][10] = min(get(i-1, {7, 10}), min(get(i-1, {0, 1, 3, 4, 5, 6, 8, 11})+1, get(i-1, {2, 9})+2));
      }
    }
  }
  for (int j=0; j<12; ++j) {
    f = min(f, dp[n-1][j]);
  }
  cout << f << '\n';
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 376 ms 98380 KB Output is correct
8 Correct 428 ms 98312 KB Output is correct
9 Correct 421 ms 98400 KB Output is correct
10 Correct 404 ms 98256 KB Output is correct
11 Correct 409 ms 98532 KB Output is correct
12 Correct 347 ms 98276 KB Output is correct
13 Correct 342 ms 98264 KB Output is correct
14 Correct 357 ms 98268 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -