結果

問題 No.2162 Copy and Paste 2
ユーザー vjudge1vjudge1
提出日時 2024-10-04 17:56:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 195 ms / 7,000 ms
コード長 1,580 bytes
コンパイル時間 1,448 ms
コンパイル使用メモリ 168,252 KB
実行使用メモリ 36,864 KB
最終ジャッジ日時 2024-10-04 17:56:31
合計ジャッジ時間 6,010 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=(j);i<=(k);++i)
#define NFOR(i,j,k) for(int i=(j);i>=(k);--i)
#define mkp make_pair
#define fst first
#define sec second
#define inl inline
#define pb push_back
#define el_phy_kongroo return 0
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned int ui;
typedef pair< int,int > pii;
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0',ch=getchar();}
	return s*w;
}
void file()
{
	freopen("proud.in","r",stdin);
	freopen("proud.out","w",stdout);
}
void teltim(int x)
{
	clock_t c1=0;
	if(x) c1=clock();
	else cerr<<endl<<clock()-c1<<"ms"<<endl;
}
const int N=2e6+5;

char s[N];
int n;

int z[N];
void sov()
{
	z[0]=n;
	int i=1,j=0;
	while(i<n)
	{
		while(i+j<n&&s[j]==s[i+j]) j++;
		z[i]=j;
		if(j==0) 
		{
			i++;
			continue;
		}
		int k=1;
		while(i+k<n&&k+z[k]<j)
		{
			z[i+k]=z[k];
			k++;
		}
		i+=k;j-=k;
	}
}

int mx[20][N],nxt[20][N],mn[N];

int main()
{
	//file();
	scanf("%s",s);
	n=strlen(s);
	sov();
	FOR(i,0,n-1) mx[0][i]=z[i];
	FOR(i,0,n-1)
	{
		if(i==n-1) nxt[0][i]=i;
		else nxt[0][i]=i+1;
	}
	FOR(i,1,19) FOR(j,0,n-1)
	{
		int k=nxt[i-1][j];
		nxt[i][j]=nxt[i-1][k];
		mx[i][j]=max(mx[i-1][j],mx[i-1][k]);
	}
	FOR(i,1,n-1)
	{
		mn[i]=min(mn[i],mn[i-1]);
		int x=mn[i]+1,j=i+1,z=i+1;
		while(j<n)
		{
			if(mx[19][j]<z) break;
			NFOR(k,19,0) if(mx[k][j]<z) j=nxt[k][j];
			j+=z-1;
			x-=z-1;
			mn[j]=min(mn[j],x);
			j++;
		}
	}
	printf("%d",n+mn[n-1]);
	el_phy_kongroo;
}
0