제출 #1254448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254448		_rain_	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	85 / 85	280 ms	141544 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))

template<class X,class Y>
	bool maximize(X &x, Y y){
		if (x<y) return x = y , true; else return false;
	}
template<class X,class Y>	
	bool minimize(X &x, Y y){
		if (x>y) return x = y , true; else return false;
	}
	
const int N = (int) 3000;
	int length_s1 , length_s2 , need_length;
	string s1 , s2;
	int p[N + 2] = {};
	
	int lss[N+2][N+2] , lps[N+2][N+2] , lsp[N+2][N+2] , lpp[N+2][N+2];
	
struct ANS{
	int length;
	int p1 , p2;
};

int get_id(int tt , int cur , int rev){
	int length = (tt == 1 ? length_s1 : length_s2);
	if (rev) return length - cur + 1; else return cur;
}

ANS calc(string s1,string s2,int t){
	s1 = '#' + s1 , s2 = '#' + s2;
	memset(lss,0,sizeof lss);
	memset(lsp,0,sizeof lsp);
	memset(lpp,0,sizeof lpp);
	memset(lps,0,sizeof lps);
	
//	cout << s1 << ' ' << s2 << '\n';
	
	for(int i = 1; i <= length_s1; ++i){
		for(int j = 1; j <= length_s2; ++j){
			if (s1[i] == s2[j]) lss[i][j] = lss[i-1][j-1] + 1;
		}
	}
	for(int i = length_s1; i >= 1; --i){
		for(int j = length_s2; j >= 1; --j){
			if (s1[i] == s2[j]) lpp[i][j] = lpp[i+1][j+1] + 1;
		}
	}
	for(int i = 1; i <= length_s1; ++i){
		for(int j = 1; j <= length_s2; ++j){
			maximize(lsp[i][j - lss[i][j] + 1] , lss[i][j]);
			maximize(lps[i][j + lpp[i][j] - 1] , lpp[i][j]);
		}
	}
	for(int i = 1; i<= length_s1; ++i){
		for(int j = 1; j <= length_s2; ++j){
			maximize(lsp[i][j] , lsp[i][j - 1] - 1);
		}
	}
	for(int j = 1; j <= length_s2; ++j){
		for(int i = 1; i <= length_s1; ++i){
			maximize(lps[i][j] , lps[i - 1][j] - 1);
		}
	}
	ANS ans;
	ans.length = -1;
	for(int i = 1; i <= length_s1; ++i){
		for(int j = 1; j <= length_s2; ++j){
			if (maximize(ans.length , lsp[i][j] + lps[i+1][j-1])){
				if (i - lsp[i][j] + 1 > 0 && j - lps[i+1][j-1] > 0){
					ans.p1 = i - lsp[i][j] + 1;
					if (t==0) ans.p2 =  j - lps[i+1][j-1];
						else ans.p2 = get_id(2 , j + lsp[i][j] - 1 , 1);
				}
			}
		}
	}
	return ans;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ; 
	#define name "main"
		if (fopen(name".inp" , "r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> s1 >> s2;
		length_s1 = sz(s1)  , length_s2 = sz(s2) ;
		
		ANS ans1 = calc(s1,s2,0);
		reverse(s2.begin() , s2.end());
		ANS ans2 = calc(s1,s2,1);
		if (ans1.length < ans2.length) swap(ans1,ans2);
		cout<<ans1.length<<'\n';
		cout<<ans1.p1 - 1<<' '<<ans1.p2 - 1<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int main()':
necklace.cpp:93:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:94:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40