Submission #856540


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
string w;
int L;
vector<vector<int>> G;
map<int, pair<int,int>> memo;
pair<int,int> f(int p) {
	if (p == L) return {0, 1};
	if (memo.count(p)) return memo[p];
	int r1 = 1 << 30;
	int r2 = 0;
	for (int x : G[p]) {
		auto q = f(x);
		++ q.first;
		if (q.first < r1) {
			r1 = q.first;
			r2 = q.second;
		} else if (q.first == r1) {
			r2 += q.second;
			r2 %= mod;
		}
	}
	return memo[p] = {r1, r2};
}
int main() {
	cin >> w;
	L = w.length();
	if (L > 4000) throw 1;
	G.resize(L);
	for (int i = 0; i < L; ++ i) {
		vector<bool> hoge(L+1, true);
		for (int len = 1; i + len*2 <= L; ++ len) {
			string s = w.substr(i, len);
			for (int k = 2; i + len*k <= L; ++ k) {
				if (w.substr(i+(k-1)*len, len) != s) break;
				hoge[i+len*k] = false;
			}
		}
		for (int j = i+1; j <= L; ++ j) {
			if (hoge[j]) G[i].push_back(j);
		}
	}
	auto r = f(0);
	cout << r.first << endl;
	cout << r.second << endl;
}

Submission Info

Submission Time
Task F - Best Representation
User hasi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1019 Byte
Status TLE
Exec Time 2109 ms
Memory 41088 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 400 0 / 500
Status
AC × 3
AC × 10
TLE × 26
AC × 10
TLE × 26
RE × 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 83 ms 2048 KB
subtask1_04.txt TLE 2101 ms 384 KB
subtask1_05.txt TLE 2103 ms 384 KB
subtask1_06.txt TLE 2101 ms 384 KB
subtask1_07.txt TLE 2101 ms 384 KB
subtask1_08.txt TLE 2101 ms 384 KB
subtask1_09.txt TLE 2101 ms 384 KB
subtask1_10.txt TLE 2105 ms 40832 KB
subtask1_11.txt TLE 2105 ms 40960 KB
subtask1_12.txt TLE 2105 ms 40960 KB
subtask1_13.txt TLE 2109 ms 40960 KB
subtask1_14.txt TLE 2109 ms 40960 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 TLE 2102 ms 7808 KB
subtask1_20.txt TLE 2102 ms 7808 KB
subtask1_21.txt TLE 2103 ms 15488 KB
subtask1_22.txt TLE 2103 ms 14720 KB
subtask1_23.txt TLE 2103 ms 15232 KB
subtask1_24.txt TLE 2103 ms 15488 KB
subtask1_25.txt TLE 2104 ms 24320 KB
subtask1_26.txt TLE 2105 ms 38400 KB
subtask1_27.txt TLE 2105 ms 37888 KB
subtask1_28.txt TLE 2105 ms 39680 KB
subtask1_29.txt TLE 2105 ms 39424 KB
subtask1_30.txt TLE 2109 ms 37760 KB
subtask1_31.txt TLE 2105 ms 40320 KB
subtask1_32.txt TLE 2105 ms 39936 KB
subtask1_33.txt TLE 2106 ms 41088 KB
subtask2_01.txt RE 212 ms 900 KB
subtask2_02.txt RE 215 ms 900 KB
subtask2_03.txt RE 217 ms 900 KB
subtask2_04.txt RE 216 ms 900 KB
subtask2_05.txt RE 215 ms 900 KB
subtask2_06.txt RE 216 ms 900 KB
subtask2_07.txt RE 215 ms 900 KB
subtask2_08.txt RE 216 ms 900 KB
subtask2_09.txt RE 215 ms 900 KB
subtask2_10.txt RE 216 ms 900 KB
subtask2_11.txt RE 217 ms 900 KB
subtask2_12.txt RE 216 ms 900 KB
subtask2_13.txt RE 218 ms 900 KB
subtask2_14.txt RE 217 ms 900 KB
subtask2_15.txt RE 219 ms 900 KB
subtask2_16.txt RE 216 ms 900 KB
subtask2_17.txt RE 215 ms 900 KB
subtask2_18.txt RE 218 ms 900 KB
subtask2_19.txt RE 216 ms 900 KB
subtask2_20.txt RE 219 ms 900 KB
subtask2_21.txt RE 215 ms 900 KB
subtask2_22.txt RE 215 ms 900 KB
subtask2_23.txt RE 214 ms 900 KB
subtask2_24.txt RE 212 ms 900 KB
subtask2_25.txt RE 217 ms 900 KB
subtask2_26.txt RE 215 ms 900 KB
subtask2_27.txt RE 215 ms 900 KB
subtask2_28.txt RE 201 ms 900 KB
subtask2_29.txt RE 209 ms 900 KB