oj.uz

Submission #124970

# Submission time Handle Problem Language Result Execution time Memory
124970 2019-07-04T08:39:08 Z 이온조(#3049) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 4 ms 1272 KB 
#include <bits/stdc++.h>
using namespace std;

char A[3009], B[3009];
int N, M, ans, AI, BI, L[3009][3009], R[3009][3009];

int GL(int i, int j) {
	if(i < 1 || j > M) return 0;
	if(L[i][j] != -1) return L[i][j];
	if(A[i] == B[j]) L[i][j] = 1;
	else L[i][j] = 0;
	int XX = GL(i-1, j), YY = GL(i, j+1);
	if(XX && A[i] == B[j + XX]) L[i][j] = max(L[i][j], XX + 1);
	if(YY && A[i - YY] == B[j]) L[i][j] = max(L[i][j], YY + 1);
	return L[i][j];
}

int GR(int i, int j) {
	if(i > N || j < 1) return 0;
	if(R[i][j] != -1) return R[i][j];
	if(A[i] == B[j]) R[i][j] = 1;
	else R[i][j] = 0;
	int XX = GR(i+1, j), YY = GR(i, j-1);
	if(XX && A[i] == B[j - XX]) R[i][j] = max(R[i][j], XX + 1);
	if(YY && A[i + YY] == B[j]) R[i][j] = max(R[i][j], YY + 1);
	return R[i][j];
}

void solve(int x) {
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) L[i][j] = R[i][j] = -1;
	for(int i=1; i<N; i++) {
		for(int j=1; j<M; j++) {
			int vl = (GL(i, j+1) < 0 ? 0 : GL(i, j+1)), vr = (GR(i+1, j) < 0 ? 0 : GR(i+1, j));
			int v = vl + vr;
			if(ans < v) {
				ans = v;
				AI = i - vl + 1;
				if(x) BI = M - (j + vr);
				else BI = j - vr + 1;
			}
		}
	}
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=M; j++) {
			int v = GL(i, j);
			// printf("GL(%d, %d): %d\n", i, j, v);
			if(ans < v) {
				ans = v;
				AI = i - v + 1;
				if(x) BI = M - (j + v) + 2;
				else BI = j;
			}
		}
	}
}

int main() {
	scanf("%s %s", A+1, B+1);
	N = strlen(A+1), M = strlen(B+1);
	A[0] = A[N+1] = '?'; B[0] = B[M+1] = '!';
	solve(0);
	reverse(B, B+M+2);
	solve(1);
	printf("%d\n%d %d", ans, AI - 1, BI - 1);
	return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s %s", A+1, B+1);
  ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -