oj.uz

Submission #123001

# Submission time Handle Problem Language Result Execution time Memory
123001 2019-06-30T01:12:05 Z model_code Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 530 ms 35920 KB 
//DP: time O(n^2), mem O(n^2) 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solve_noflip(string &s, string &t, int *loc) {
  int n = s.size();
  int m = t.size();
  int res = 0;
  vector< vector< short > > forw_back_len(n + 1, vector< short >(m + 1));
  vector< vector< short > > back_forw_len(n + 1, vector< short >(m + 1));
  // d = j-i
  for (int d = -n + 1; d < m; ++d) {
    short cur_len = 0;
    for (int i = min(n, m - d) - 1; i >= max(0, -d); --i) {
      int j = i + d;
      if (s[i] == t[j]) {
        ++cur_len;
      } else {
        cur_len = 0;
      }
      int ni = i + cur_len;
      int nj = j + cur_len;
      forw_back_len[i][nj] = max(forw_back_len[i][nj], cur_len);
      back_forw_len[ni][j] = max(back_forw_len[ni][j], cur_len);
    }
  }
  for (int i = n; i >= 0; --i) {
    for (int j = m; j >= 0; --j) {
      if (j < m - 1)
        forw_back_len[i][j] = max((int)forw_back_len[i][j], forw_back_len[i][j + 1] - 1);
      if (i < n - 1)
        back_forw_len[i][j] = max((int)back_forw_len[i][j], back_forw_len[i + 1][j] - 1);
      if (forw_back_len[i][j] + back_forw_len[i][j] > res) {
        res = forw_back_len[i][j] + back_forw_len[i][j];
        loc[0] = i - back_forw_len[i][j];
        loc[1] = j - forw_back_len[i][j];
      }
    }
  }
  return res;
}

int solve(string &s, string &t, int *loc) {
  int loc_noflip[2];
  int res = solve_noflip(s, t, loc_noflip);
  reverse(t.begin(), t.end());
  int loc_flip[2];
  int res_flip = solve_noflip(s, t, loc_flip);
  if (res_flip > res) {
    res = res_flip;
    loc[0] = loc_flip[0];
    loc[1] = (int)t.size() - loc_flip[1] - res;
  } else {
    for (int i = 0; i < 2; ++i) loc[i] = loc_noflip[i];
  }
  return res;
}

int main() {
  cin.sync_with_stdio(false);
  string s, t;
  cin >> s >> t;
  int loc[2];
  int res = solve(s, t, loc);
  cout << res << '\n';
  if (res) {
    cout << loc[0] << ' ' << loc[1] << '\n';
  }
  return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 6 ms 1016 KB Output is correct
8 Correct 6 ms 888 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 7 ms 1016 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Correct 6 ms 1016 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 6 ms 1016 KB Output is correct
8 Correct 6 ms 888 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 7 ms 1016 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Correct 6 ms 1016 KB Output is correct
13 Correct 391 ms 35920 KB Output is correct
14 Correct 529 ms 35900 KB Output is correct
15 Correct 322 ms 33792 KB Output is correct
16 Correct 451 ms 35248 KB Output is correct
17 Correct 525 ms 34652 KB Output is correct
18 Correct 530 ms 35680 KB Output is correct
19 Correct 455 ms 35524 KB Output is correct
20 Correct 384 ms 34556 KB Output is correct
21 Correct 379 ms 34824 KB Output is correct