oj.uz

Submission #1073365

# Submission time Handle Problem Language Result Execution time Memory
1073365 2024-08-24T13:34:19 Z duckindog Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 177 ms 106720 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3000 + 10;
string s, t;

int ps[N][N], sp[N][N], ss[N][N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> s >> t;
  int n = s.size(), m = t.size();
  s = '@' + s; t = '@' + t;

  tuple<int, int, int> answer;

  for (int type = 0; type < 2; ++ type) {
    for (int i = 1; i <= n; ++i) { 
      for (int j = 1; j <= m; ++j) {
        ps[i][j] = sp[i][j] = ss[i][j] = 0;
        if (s[i] == t[j]) ss[i][j] = ss[i - 1][j - 1] + 1;
      }
    }

    for (int i = 1; i <= n; ++i) { 
      for (int j = 1; j <= m; ++j) { 
        if (!ss[i][j]) continue;
        ps[i - ss[i][j] + 1][j] = max(ps[i - ss[i][j] + 1][j], ss[i][j]);
        sp[i][j - ss[i][j] + 1] = max(sp[i][j - ss[i][j] + 1], ss[i][j]);
      }
    }

    for (int i = 1; i < n; ++i) { 
      for (int j = 1; j < m; ++j) { 
        int length = ps[i + 1][j] + sp[i][j + 1],
               stS = i - sp[i][j + 1], 
               stT = j - ps[i + 1][j];

        if (type) stT = m - (stT + length);
        answer = max(answer, make_tuple(length, stS, stT));
      }
    }
    // break;
    reverse(t.begin() + 1, t.end());
  }

  auto [length, i, j] = answer;
  cout << length << "\n";
  cout << i << " " << j << "\n";
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 4 ms 13148 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 4 ms 14032 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 5 ms 12892 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 4 ms 13148 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 4 ms 14032 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 5 ms 12892 KB Output is correct
13 Correct 165 ms 106720 KB Output is correct
14 Correct 136 ms 106548 KB Output is correct
15 Correct 153 ms 104016 KB Output is correct
16 Correct 146 ms 106576 KB Output is correct
17 Correct 128 ms 105496 KB Output is correct
18 Correct 137 ms 106524 KB Output is correct
19 Correct 133 ms 106332 KB Output is correct
20 Correct 170 ms 105696 KB Output is correct
21 Correct 177 ms 106068 KB Output is correct