Submission #857195


Source Code Expand

Copy
#include <cmath>
#include <vector>
#include <iostream>
#include <limits>
#include <iostream>
#include <vector>
#include <cassert>
#include <complex>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long Long;

int mat[4010][4010];
void comp(string &S, int s){
	int i = 0, j = -1;
	vector<int> T(S.size()+1);
	T[0] = -1;
	while(i+s < S.size()){
		while(j >= 0 && S[i+s] != S[j+s]){
			j = T[j];
		}
		i++;j++;
		T[i] = j;
		int ss = i;
		int p = ss - j;
		if(p > 0 && p != ss && ss % p == 0){
			mat[s][s+i-1] = p;
		}else{
			mat[s][s+i-1] = -1;
		}
	}
}
int mem[4010];
int cat[4010];
int dp(int i){
	if(i < 0)return 0;
	int w = 1000000;
	if(mem[i] != -1)return mem[i];
	int c = 0;
	for(int j = 0; j < i; ++j){
		if(mat[j][i] == -1){
			int t = dp(j-1) + 1;
			if(t < w){
				w = t;
				c = 1;
			}else if(t == w){
				c++;
			}
		}
	}
	cat[i] = c;
	return mem[i] = w;
}

int main(){
	
	string S;
	cin >> S;
	for(int i = 0; i < S.size(); ++i){
		comp(S,i);
	}
	memset(mem,-1,sizeof(mem));
	cout << dp(S.size()-1) << endl;
	cout << cat[S.size()-1] << endl;
	
}


/*


 */

Submission Info

Submission Time
Task F - Best Representation
User cjtoribio
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1241 Byte
Status WA
Exec Time 2106 ms
Memory 45568 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 400 0 / 500
Status
AC × 1
WA × 2
AC × 11
WA × 25
AC × 11
WA × 25
TLE × 29
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt
All example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
example_02.txt WA 4 ms 256 KB
example_03.txt WA 4 ms 256 KB
subtask1_01.txt WA 4 ms 256 KB
subtask1_02.txt WA 4 ms 256 KB
subtask1_03.txt WA 17 ms 4352 KB
subtask1_04.txt WA 156 ms 44928 KB
subtask1_05.txt AC 322 ms 44928 KB
subtask1_06.txt AC 150 ms 44928 KB
subtask1_07.txt WA 151 ms 45568 KB
subtask1_08.txt AC 325 ms 45568 KB
subtask1_09.txt AC 152 ms 45568 KB
subtask1_10.txt AC 306 ms 45568 KB
subtask1_11.txt WA 307 ms 45568 KB
subtask1_12.txt WA 307 ms 45568 KB
subtask1_13.txt WA 318 ms 45568 KB
subtask1_14.txt WA 293 ms 45568 KB
subtask1_15.txt WA 4 ms 256 KB
subtask1_16.txt WA 4 ms 256 KB
subtask1_17.txt AC 4 ms 256 KB
subtask1_18.txt WA 4 ms 256 KB
subtask1_19.txt WA 301 ms 45568 KB
subtask1_20.txt AC 289 ms 45568 KB
subtask1_21.txt WA 295 ms 45568 KB
subtask1_22.txt AC 295 ms 45568 KB
subtask1_23.txt AC 310 ms 45568 KB
subtask1_24.txt AC 295 ms 45568 KB
subtask1_25.txt WA 221 ms 45568 KB
subtask1_26.txt WA 306 ms 45568 KB
subtask1_27.txt WA 295 ms 44416 KB
subtask1_28.txt WA 307 ms 45056 KB
subtask1_29.txt WA 309 ms 45056 KB
subtask1_30.txt WA 276 ms 42368 KB
subtask1_31.txt WA 309 ms 44928 KB
subtask1_32.txt WA 299 ms 44672 KB
subtask1_33.txt WA 307 ms 45568 KB
subtask2_01.txt TLE 2102 ms 11012 KB
subtask2_02.txt TLE 2102 ms 10980 KB
subtask2_03.txt TLE 2102 ms 9316 KB
subtask2_04.txt TLE 2106 ms 10980 KB
subtask2_05.txt TLE 2102 ms 10976 KB
subtask2_06.txt TLE 2102 ms 9440 KB
subtask2_07.txt TLE 2106 ms 11104 KB
subtask2_08.txt TLE 2106 ms 10336 KB
subtask2_09.txt TLE 2106 ms 10336 KB
subtask2_10.txt TLE 2102 ms 10336 KB
subtask2_11.txt TLE 2102 ms 10336 KB
subtask2_12.txt TLE 2102 ms 10976 KB
subtask2_13.txt TLE 2102 ms 10464 KB
subtask2_14.txt TLE 2102 ms 10592 KB
subtask2_15.txt TLE 2102 ms 10336 KB
subtask2_16.txt TLE 2102 ms 10336 KB
subtask2_17.txt TLE 2102 ms 9696 KB
subtask2_18.txt TLE 2106 ms 10336 KB
subtask2_19.txt TLE 2102 ms 10464 KB
subtask2_20.txt TLE 2102 ms 10080 KB
subtask2_21.txt TLE 2106 ms 10352 KB
subtask2_22.txt TLE 2106 ms 10208 KB
subtask2_23.txt TLE 2106 ms 10208 KB
subtask2_24.txt TLE 2106 ms 10640 KB
subtask2_25.txt TLE 2102 ms 10420 KB
subtask2_26.txt TLE 2102 ms 10308 KB
subtask2_27.txt TLE 2102 ms 10708 KB
subtask2_28.txt TLE 2102 ms 13440 KB
subtask2_29.txt TLE 2102 ms 11264 KB