oj.uz

Submission #965013

# Submission time Handle Problem Language Result Execution time Memory
965013 2024-04-18T03:03:34 Z abczz Lamps (JOI19_lamps) C++14
4 / 100
 429 ms 98424 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, {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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 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 468 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 344 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 472 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 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 468 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 344 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 472 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 1 ms 460 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
7 Correct 416 ms 98192 KB Output is correct
8 Correct 393 ms 98388 KB Output is correct
9 Correct 408 ms 98352 KB Output is correct
10 Correct 398 ms 98264 KB Output is correct
11 Correct 429 ms 98424 KB Output is correct
12 Correct 350 ms 98212 KB Output is correct
13 Correct 353 ms 98204 KB Output is correct
14 Correct 349 ms 98212 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 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 468 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 344 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 472 KB Output isn't correct
18 Halted 0 ms 0 KB -