oj.uz

Submission #965003

# Submission time Handle Problem Language Result Execution time Memory
965003 2024-04-18T02:52:03 Z abczz Lamps (JOI19_lamps) C++14
4 / 100
 392 ms 98404 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}), get(i-1, {1, 2, 4, 6, 9, 10, 11})+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}), get(i-1, {0, 2, 3, 5, 9, 10, 11})+1);
        dp[i][3] = min(get(i-1, {3}), min(get(i-1, {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 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 428 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 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 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 428 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 368 ms 98300 KB Output is correct
8 Correct 386 ms 98268 KB Output is correct
9 Correct 355 ms 98376 KB Output is correct
10 Correct 364 ms 98208 KB Output is correct
11 Correct 392 ms 98404 KB Output is correct
12 Correct 315 ms 98212 KB Output is correct
13 Correct 360 ms 98392 KB Output is correct
14 Correct 379 ms 98204 KB Output is correct

Subtask #4
0 / 49.0

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