제출 #100660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100660		cki86201	원형 문자열 (IZhO13_rowords)	C++11	100 / 100	206 ms	96772 KiB

rowords

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

char X[4020], Y[2040];
int N, M, ans;
int dp[4020][2040], pre[4020][2040], c[4020][2040];

void solve() {
	memset(dp, 0, sizeof dp);
	memset(pre, 0, sizeof pre);
	memset(c, 0, sizeof c);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) {
		dp[i][j] = dp[i][j-1];
		if(dp[i-1][j-1] + 1 > dp[i][j] && X[i] == Y[j]) dp[i][j] = dp[i-1][j-1] + 1, pre[i][j] = 1;
		if(dp[i-1][j] > dp[i][j]) dp[i][j] = dp[i-1][j], pre[i][j] = 2;
	}
	for(int i=1;i<=N/2;i++) {
		int sum = 0;
		for(int j=1;j<=M;j++) sum += c[i+N/2-1][j];
		ans = max(ans, dp[i+N/2-1][M] + sum);
		int f = -1;
		for(int j=1;j<=M;j++) if(X[i] == Y[j]) {
			f = j; break;
		}
		if(f == -1) continue;
		pre[i][f] = 0; c[i][f]--;
		for(int j=i+1;j<=N;j++) {
			if(pre[j][f] != 2) {
				++f;
				while(f <= M && pre[j][f] == 0) ++f;
			}
			if(f > M) break;
			pre[j][f] = 0; c[j][f]--;
		}
	}
	
}

int main() {
	scanf("%s%s", X+1, Y+1);
	N = (int)strlen(X+1), M = (int)strlen(Y+1);
	for(int i=1;i<=N;i++) X[i+N] = X[i];
	N *= 2;
	solve();
	reverse(Y+1, Y+1+M);
	solve();
	printf("%d\n", ans);
	return 0;
}

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

rowords.cpp: In function 'int main()':
rowords.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", X+1, Y+1);
  ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100