提出 #856321


ソースコード 拡げる

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;
bool check(int p, int len) {
	for (int k = 2; k <= len; ++ k) if (len % k == 0) {
		for (int i = 1; i < k; ++ i) {
			if (w.substr(p + (i-1) * (len / k), len / k) != w.substr(p + i * (len / k), len / k)) goto next;
		}
		return false;
		next:;
	}
	return true;
}
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) {
		for (int j = i+1; j <= L; ++ j) {
			if (check(i, j-i)) G[i].push_back(j);
		}
	}
	auto r = f(0);
	cout << r.first << endl;
	cout << r.second << endl;
}

提出情報

提出日時
問題 F - 最良表現
ユーザ hasi
言語 C++14 (GCC 5.4.1)
得点 0
コード長 1053 Byte
結果 TLE
実行時間 2105 ms
メモリ 2048 KB

ジャッジ結果

セット名 Sample Subtask1 All
得点 / 配点 0 / 0 0 / 400 0 / 500
結果
AC × 3
AC × 10
TLE × 26
AC × 10
TLE × 26
RE × 29
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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 1009 ms 2048 KB
subtask1_04.txt TLE 2101 ms 384 KB
subtask1_05.txt TLE 2105 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 2101 ms 768 KB
subtask1_11.txt TLE 2101 ms 768 KB
subtask1_12.txt TLE 2101 ms 768 KB
subtask1_13.txt TLE 2101 ms 768 KB
subtask1_14.txt TLE 2101 ms 768 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 2101 ms 512 KB
subtask1_20.txt TLE 2101 ms 512 KB
subtask1_21.txt TLE 2101 ms 768 KB
subtask1_22.txt TLE 2101 ms 768 KB
subtask1_23.txt TLE 2101 ms 768 KB
subtask1_24.txt TLE 2101 ms 768 KB
subtask1_25.txt TLE 2101 ms 384 KB
subtask1_26.txt TLE 2105 ms 512 KB
subtask1_27.txt TLE 2105 ms 640 KB
subtask1_28.txt TLE 2105 ms 640 KB
subtask1_29.txt TLE 2105 ms 640 KB
subtask1_30.txt TLE 2101 ms 896 KB
subtask1_31.txt TLE 2101 ms 896 KB
subtask1_32.txt TLE 2101 ms 896 KB
subtask1_33.txt TLE 2101 ms 768 KB
subtask2_01.txt RE 331 ms 900 KB
subtask2_02.txt RE 216 ms 900 KB
subtask2_03.txt RE 215 ms 900 KB
subtask2_04.txt RE 216 ms 900 KB
subtask2_05.txt RE 216 ms 900 KB
subtask2_06.txt RE 217 ms 900 KB
subtask2_07.txt RE 216 ms 900 KB
subtask2_08.txt RE 215 ms 900 KB
subtask2_09.txt RE 215 ms 900 KB
subtask2_10.txt RE 213 ms 900 KB
subtask2_11.txt RE 217 ms 900 KB
subtask2_12.txt RE 219 ms 900 KB
subtask2_13.txt RE 223 ms 900 KB
subtask2_14.txt RE 222 ms 900 KB
subtask2_15.txt RE 217 ms 900 KB
subtask2_16.txt RE 223 ms 900 KB
subtask2_17.txt RE 217 ms 900 KB
subtask2_18.txt RE 216 ms 900 KB
subtask2_19.txt RE 220 ms 900 KB
subtask2_20.txt RE 219 ms 900 KB
subtask2_21.txt RE 221 ms 900 KB
subtask2_22.txt RE 223 ms 900 KB
subtask2_23.txt RE 219 ms 900 KB
subtask2_24.txt RE 215 ms 900 KB
subtask2_25.txt RE 218 ms 900 KB
subtask2_26.txt RE 214 ms 900 KB
subtask2_27.txt RE 216 ms 900 KB
subtask2_28.txt RE 203 ms 900 KB
subtask2_29.txt RE 211 ms 900 KB