oj.uz

답안 #525805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525805 2022-02-12T23:05:49 Z Yazan_Alattar Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 2 ms 2636 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 305;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int dpS[M][M];
int dpPS[M][M];
int dpSP[M][M];

array <int, 3> solve (string s, string t){
	int n = s.size(), m = t.size();
	array <int, 3> ret = {0, 0, 0};
	
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) dpS[i][j] = dpSP[i][j] = dpPS[i][j] = 0;

	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			if(s[i] == t[j])
				dpS[i][j] = (i && j ? dpS[i - 1][j - 1] + 1 : 1);
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j) if(dpS[i][j]){
			dpPS[i - dpS[i][j] + 1][j] = max(dpPS[i - dpS[i][j] + 1][j], dpS[i][j]);
			dpSP[i][j - dpS[i][j] + 1] = max(dpSP[i][j - dpS[i][j] + 1], dpS[i][j]);
	}
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j){
			if(i) dpPS[i][j] = max(dpPS[i][j], dpPS[i - 1][j] - 1);
			if(j) dpSP[i][j] = max(dpSP[i][j], dpSP[i][j - 1] - 1);
	}
	
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			int len = dpSP[i][j];
			if(i + 1 < n && j) len += dpPS[i + 1][j - 1];
			if(len > ret[0]){
				ret[0] = len;
				ret[1] =  i - dpSP[i][j] + 1;
				ret[2] = j + dpSP[i][j] - len;
			}
		}
	}
	
	return ret;
}
 
int main()
{
	string s, t;
	cin >> s >> t;
	array <int, 3> ans = solve(s, t);
	
	reverse(all(t));
	array <int, 3> tmp = solve(s, t);
	tmp[2] = t.size() - tmp[2] - tmp[0];
	
	ans = max(ans, tmp);
	cout << ans[0] << endl << ans[1] << " " << ans[2] << endl;
	return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Runtime error 2 ms 2636 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Runtime error 2 ms 2636 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -