Submission #857259


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;
		}
	}
}
pair<int,int> mem[4010];
pair<int,int> dp(int i){
	if(i < 0)return make_pair(0,1);
	int w = 1000000;
	if(mem[i].first != -1)return mem[i];
	int c = 0;
	for(int j = 0; j <= i; ++j){
		if(mat[j][i] == -1){
			pair<int,int> t = dp(j-1);
			if(t.first+1 < w){
				w = t.first+1;
				c = t.second;
			}else if(t.first+1 == w){
				c += t.second;
				c %= 1000000007;
			}
		}
	}
	return mem[i] = make_pair(w,c);
}

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


/*


 */

Submission Info

Submission Time
Task F - Best Representation
User cjtoribio
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1383 Byte
Status TLE
Exec Time 2106 ms
Memory 45824 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 500
Status
AC × 3
AC × 36
AC × 36
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 AC 4 ms 256 KB
example_03.txt AC 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 16 ms 4352 KB
subtask1_04.txt AC 286 ms 45184 KB
subtask1_05.txt AC 319 ms 44928 KB
subtask1_06.txt AC 289 ms 45184 KB
subtask1_07.txt AC 298 ms 45824 KB
subtask1_08.txt AC 314 ms 45568 KB
subtask1_09.txt AC 288 ms 45824 KB
subtask1_10.txt AC 323 ms 45568 KB
subtask1_11.txt AC 324 ms 45568 KB
subtask1_12.txt AC 323 ms 45568 KB
subtask1_13.txt AC 323 ms 45568 KB
subtask1_14.txt AC 308 ms 45568 KB
subtask1_15.txt AC 4 ms 256 KB
subtask1_16.txt AC 4 ms 256 KB
subtask1_17.txt AC 4 ms 256 KB
subtask1_18.txt AC 4 ms 256 KB
subtask1_19.txt AC 292 ms 45568 KB
subtask1_20.txt AC 312 ms 45568 KB
subtask1_21.txt AC 308 ms 45568 KB
subtask1_22.txt AC 312 ms 45568 KB
subtask1_23.txt AC 328 ms 45568 KB
subtask1_24.txt AC 309 ms 45568 KB
subtask1_25.txt AC 318 ms 45568 KB
subtask1_26.txt AC 325 ms 45568 KB
subtask1_27.txt AC 312 ms 44416 KB
subtask1_28.txt AC 331 ms 45056 KB
subtask1_29.txt AC 331 ms 45056 KB
subtask1_30.txt AC 290 ms 42368 KB
subtask1_31.txt AC 316 ms 44928 KB
subtask1_32.txt AC 324 ms 44672 KB
subtask1_33.txt AC 324 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 9444 KB
subtask2_04.txt TLE 2102 ms 10980 KB
subtask2_05.txt TLE 2102 ms 10976 KB
subtask2_06.txt TLE 2102 ms 9440 KB
subtask2_07.txt TLE 2102 ms 10976 KB
subtask2_08.txt TLE 2102 ms 10336 KB
subtask2_09.txt TLE 2102 ms 10336 KB
subtask2_10.txt TLE 2102 ms 10336 KB
subtask2_11.txt TLE 2102 ms 10208 KB
subtask2_12.txt TLE 2102 ms 10976 KB
subtask2_13.txt TLE 2102 ms 10464 KB
subtask2_14.txt TLE 2102 ms 10464 KB
subtask2_15.txt TLE 2106 ms 10208 KB
subtask2_16.txt TLE 2102 ms 10208 KB
subtask2_17.txt TLE 2102 ms 9696 KB
subtask2_18.txt TLE 2102 ms 10208 KB
subtask2_19.txt TLE 2102 ms 10464 KB
subtask2_20.txt TLE 2102 ms 10080 KB
subtask2_21.txt TLE 2102 ms 10352 KB
subtask2_22.txt TLE 2102 ms 10208 KB
subtask2_23.txt TLE 2102 ms 10208 KB
subtask2_24.txt TLE 2102 ms 10512 KB
subtask2_25.txt TLE 2102 ms 10420 KB
subtask2_26.txt TLE 2106 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