# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
82761 | 2018-11-01T15:10:02 Z | naoai | Languages (IOI10_languages) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #include "grader.h" #include "lang.h" typedef unsigned long long u64; static const int mod = 666013; static const int nmax = 100; static const int lgmax = 1; static const int nrlang = 56; static const int base = 218279; bool viz[nrlang]; int c[nmax + 1]; vector<u64> h[mod]; /*void baga (int l, u64 x) { int key = (x * 61 + l) % mod; for (auto i : h[key]) if (i == x) return ; h[key].push_back(x); }*/ bool cauta (int l, u64 x) { int key = (x * 61 + l) % mod; for (auto i : h[key]) if (i == x) return 1; return 0; } void excerpt(int *E) { int bstcost = -1, bstlang = 0; for (int l = 0; l < nrlang; ++ l) { if (viz[l] == 0) continue; c[0] = 0; for (int i = 1; i <= nmax; ++ i) { u64 hsh = 0; c[i] = 0; for (int j = i - 1; j >= max(0, j - lgmax); -- j) { hsh = hsh * base + E[j]; c[i] = max(c[i], c[j] + cauta(l, hsh) * (i - j) * (i - j)); } } if (c[nmax] > bstcost) { bstcost = c[nmax]; bstlang = l; } } int ans = language(bstlang); viz[ans] = 1; for (int i = 1; i <= nmax; ++ i) { u64 hsh = 0; for (int j = i - 1; j >= max(0, j - lgmax); -- j) { hsh = hsh * base + E[j]; baga(ans, hsh); } } }