Submission #123001

#	Time	Username	Problem	Language	Result	Execution time	Memory
123001		model_code	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	530 ms	35920 KiB

necklace

//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 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40