oj.uz

Submission #124883

# Submission time Handle Problem Language Result Execution time Memory
124883 2019-07-04T05:20:48 Z 임유진(#3051) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 469 ms 106360 KB 
#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 3005

int N, M;
char A[MAXN], B[MAXN];
char Ainv[MAXN], Binv[MAXN];
int dprl[MAXN][MAXN], dprlinv[MAXN][MAXN];
int dprr[MAXN][MAXN];

void gdprl(char A[], char B[], int dprl[][MAXN]){
	//printf("gdprl(A = %s, B = %s)\n", A, B);

	for(int i = 0; i <= N; i++) dprr[i][M] = 0;
	for(int i = 0; i < M; i++) dprr[N][i] = 0;
	for(int i = N - 1; i >= 0; i--) for(int j = M - 1; j >= 0; j--) {
		if(A[i] == B[j]) dprr[i][j] = dprr[i + 1][j + 1] + 1;
		else dprr[i][j] = 0;
	}

	/*
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) printf("%d ", dprr[i][j]);
		printf("\n");
	}
	printf("***\n");
	*/

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) dprl[i][j] = 0;
		for(int j = 0; j < M; j++) if(dprr[i][j] > 0) dprl[i][j + dprr[i][j] - 1] = dprr[i][j];
		//for(int j = 0; j < M; j++) printf("%d ", dprl[i][j]);
		//printf("\n");
		//printf("***\n");
		for(int j = M - 2; j >= 0; j--) dprl[i][j] = max(dprl[i][j], dprl[i][j + 1] - 1);
		//for(int j = 0; j < M; j++) printf("%d ", dprl[i][j]);
		//printf("\n");
	}
}

int solve(char B[], char Binv[], int &p, int &q) {
	int ans = 0;

	//printf("solve(B = %s, Binv = %s)\n", B, Binv);

	gdprl(A, B, dprl);
	gdprl(Ainv, Binv, dprlinv);

	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) {
		int t1 = dprlinv[N - i - 1][M - j - 1]; 
		int t2 = (i < N - 1 && j > 0) ? dprl[i + 1][j - 1] : 0;
		if(t1 + t2 > ans) {
			ans = t1 + t2;
			p = i - t1 + 1;
			q = j - t2;
			//printf("i = %d, j = %d, t1 = %d, t2 = %d\n", i, j, t1, t2);
		}
	}

	//printf("ans = %d, p = %d, q = %d\n", ans, p, q);
	return ans;
}

int main() {
	int ans1, ans2, p1, q1, p2, q2;

	scanf("%s%s", A, B);
	for(N = 0; A[N] != 0; N++);
	for(M = 0; B[M] != 0; M++);

	for(int i = 0; i < N; i++) Ainv[i] = A[N - i - 1];
	for(int i = 0; i < M; i++) Binv[i] = B[M - i - 1];

	ans1 = solve(B, Binv, p1, q1);
	ans2 = solve(Binv, B, p2, q2);
	if(ans1 > ans2) printf("%d\n%d %d", ans1, p1, q1);
	else printf("%d\n%d %d", ans2, p2, M - q2 - ans2);

	return 0;
}

Compilation message

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

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1656 KB Output is partially correct
2 Partially correct 4 ms 1656 KB Output is partially correct
3 Correct 3 ms 1400 KB Output is correct
4 Partially correct 3 ms 1656 KB Output is partially correct
5 Correct 3 ms 1660 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1656 KB Output is partially correct
2 Partially correct 4 ms 1656 KB Output is partially correct
3 Correct 3 ms 1400 KB Output is correct
4 Partially correct 3 ms 1656 KB Output is partially correct
5 Correct 3 ms 1660 KB Output is correct
6 Partially correct 14 ms 7032 KB Output is partially correct
7 Partially correct 13 ms 7032 KB Output is partially correct
8 Partially correct 14 ms 6648 KB Output is partially correct
9 Partially correct 13 ms 6776 KB Output is partially correct
10 Correct 12 ms 7032 KB Output is correct
11 Correct 12 ms 6904 KB Output is correct
12 Correct 12 ms 6776 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1656 KB Output is partially correct
2 Partially correct 4 ms 1656 KB Output is partially correct
3 Correct 3 ms 1400 KB Output is correct
4 Partially correct 3 ms 1656 KB Output is partially correct
5 Correct 3 ms 1660 KB Output is correct
6 Partially correct 14 ms 7032 KB Output is partially correct
7 Partially correct 13 ms 7032 KB Output is partially correct
8 Partially correct 14 ms 6648 KB Output is partially correct
9 Partially correct 13 ms 6776 KB Output is partially correct
10 Correct 12 ms 7032 KB Output is correct
11 Correct 12 ms 6904 KB Output is correct
12 Correct 12 ms 6776 KB Output is correct
13 Partially correct 434 ms 106280 KB Output is partially correct
14 Partially correct 377 ms 106360 KB Output is partially correct
15 Partially correct 469 ms 102592 KB Output is partially correct
16 Correct 406 ms 105764 KB Output is correct
17 Correct 355 ms 104312 KB Output is correct
18 Correct 370 ms 106028 KB Output is correct
19 Partially correct 383 ms 105848 KB Output is partially correct
20 Correct 407 ms 104312 KB Output is correct
21 Correct 417 ms 104824 KB Output is correct