제출 #646201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646201		mychecksedad	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	1579 ms	47428 KiB

necklace

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, m, ans = 0, p, q, dp[5000][5000];
string a, b;
void f(string &s, string &t, bool tp){    
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(s[i] == t[j]){
                if(i==0||j==0) dp[i][j] = 1;
                else dp[i][j] = dp[i - 1][j - 1] + 1;
            }else dp[i][j] = 0;
        }
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            int x = j - dp[i][j];
            if(ans < dp[i][j]){
                ans = dp[i][j];
                p = i - dp[i][j] + 1;
                if(!tp)
                    q = j - dp[i][j] + 1;
                else
                    q = m - j - 1;
            }
            if(x < 0) continue;
            for(int d = 1; i + d < n; ++d){
                if(dp[i + d][x] < d) continue;
                if(ans < d + dp[i][j]){
                    ans = d + dp[i][j];
                    p = i - dp[i][j] + 1;
                    if(!tp)
                        q = x - d + 1;
                    else
                        q = m - j - 1;
                    // cout << i + d << ' ' << d << ' ' << dp[i][j] << ' ' << dp[i + d][x] <<  ' ' << x << '\n';
                }
            }
        }
    }
}

void solve(){
    cin >> a >> b;
    n = a.length();
    m = b.length();
    f(a, b, 0);
    reverse(all(b));
    f(a, b, 1);
    cout << ans << '\n';
    if(ans > 0) cout << p << ' ' << q;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

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

necklace.cpp: In function 'int main()':
necklace.cpp:72:16: warning: unused variable 'aa' [-Wunused-variable]
   72 |     int T = 1, aa;
      |                ^~

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