Submission #1073365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073365		duckindog	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	177 ms	106720 KiB

necklace

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