Submission #856648


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);
	vector<vector<int>> hh(L, vector<int>(L+1));
	for (int i = 0; i < L; ++ i) {
		hh[i][0] = 0;
		for (int j = 1; i+j <= L; ++ j) {
			hh[i][j] = hh[i][j-1] * 37 + w[i+j-1];
		}
	}
	for (int i = 0; i < L; ++ i) {
		vector<bool> hoge(L+1, true);
		for (int len = 1; i + len*2 <= L; ++ len) {
			int s = hh[i][len];
			for (int k = 2; i + len*k <= L; ++ k) {
				if (hh[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 400
Code Size 1190 Byte
Status RE
Exec Time 1835 ms
Memory 103808 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 500
Status
AC × 3
AC × 36
AC × 36
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 54 ms 4224 KB
subtask1_04.txt AC 1125 ms 62464 KB
subtask1_05.txt AC 1125 ms 62464 KB
subtask1_06.txt AC 1140 ms 62464 KB
subtask1_07.txt AC 1135 ms 63744 KB
subtask1_08.txt AC 1138 ms 63744 KB
subtask1_09.txt AC 1137 ms 63744 KB
subtask1_10.txt AC 1763 ms 103680 KB
subtask1_11.txt AC 1785 ms 103680 KB
subtask1_12.txt AC 1825 ms 103680 KB
subtask1_13.txt AC 1835 ms 103680 KB
subtask1_14.txt AC 1827 ms 103808 KB
subtask1_15.txt AC 4 ms 256 KB
subtask1_16.txt AC 5 ms 256 KB
subtask1_17.txt AC 4 ms 256 KB
subtask1_18.txt AC 4 ms 256 KB
subtask1_19.txt AC 1419 ms 84736 KB
subtask1_20.txt AC 1449 ms 84736 KB
subtask1_21.txt AC 1627 ms 92416 KB
subtask1_22.txt AC 1617 ms 92416 KB
subtask1_23.txt AC 1574 ms 92416 KB
subtask1_24.txt AC 1585 ms 92416 KB
subtask1_25.txt AC 1492 ms 92544 KB
subtask1_26.txt AC 1736 ms 101504 KB
subtask1_27.txt AC 1657 ms 98304 KB
subtask1_28.txt AC 1738 ms 101504 KB
subtask1_29.txt AC 1730 ms 101248 KB
subtask1_30.txt AC 1625 ms 94336 KB
subtask1_31.txt AC 1764 ms 101760 KB
subtask1_32.txt AC 1760 ms 101120 KB
subtask1_33.txt AC 1813 ms 103808 KB
subtask2_01.txt RE 224 ms 900 KB
subtask2_02.txt RE 223 ms 900 KB
subtask2_03.txt RE 222 ms 900 KB
subtask2_04.txt RE 227 ms 900 KB
subtask2_05.txt RE 225 ms 900 KB
subtask2_06.txt RE 220 ms 900 KB
subtask2_07.txt RE 222 ms 900 KB
subtask2_08.txt RE 226 ms 900 KB
subtask2_09.txt RE 225 ms 900 KB
subtask2_10.txt RE 227 ms 900 KB
subtask2_11.txt RE 217 ms 900 KB
subtask2_12.txt RE 222 ms 900 KB
subtask2_13.txt RE 225 ms 900 KB
subtask2_14.txt RE 220 ms 900 KB
subtask2_15.txt RE 220 ms 900 KB
subtask2_16.txt RE 224 ms 900 KB
subtask2_17.txt RE 223 ms 900 KB
subtask2_18.txt RE 222 ms 900 KB
subtask2_19.txt RE 225 ms 900 KB
subtask2_20.txt RE 223 ms 900 KB
subtask2_21.txt RE 221 ms 900 KB
subtask2_22.txt RE 226 ms 900 KB
subtask2_23.txt RE 223 ms 900 KB
subtask2_24.txt RE 219 ms 900 KB
subtask2_25.txt RE 220 ms 900 KB
subtask2_26.txt RE 223 ms 900 KB
subtask2_27.txt RE 212 ms 900 KB
subtask2_28.txt RE 212 ms 900 KB
subtask2_29.txt RE 212 ms 900 KB