Submission #525803

#	Time	Username	Problem	Language	Result	Execution time	Memory
525803		Yazan_Alattar	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	0 / 85	1 ms	332 KiB

necklace

    #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 = 3005;
    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};
     
    array <int, 3> solve (string s, string t){
    	int n = s.size(), m = t.size();
    	array <int, 3> ret;
    	
    	int dpS[n][m] = {0};
    	int dpPS[n][m] = {0};
    	int dpSP[n][m] = {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: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40