Simple recursion from highest weight down to lowest with proper cut-off on maximal reachable weight and caching of results gives AC in 0.015 sec and 1Mb RAM. I write that spoiler here because I suspects that tests are very weak because I have no proof of why this straightforward thing works so fast when problem has 4-sec/256Mb limits.

It's still unclear what to output if Lara has enough time to escape (i.e. there is no reason to hide) - empty output? My AC solution ignores that case like if entrance is locked.

It's very weird - almost happened to me too (0.934 sec, dunno which test). After that I switched to 'int' and kept 'double' only for boundaries - it became 0.5 sec. Then I precalculated 1.0/(y[i+1]-y[i]) - timing didn't change. Then I suspected it was some anti-qsort case, tried to random-shuffle, even tried heapsort - no matter, still 0.5 sec. Then I've noticed that I am submitting it as GCC instead of VisualC (was testing another problem before on GCC/clang) - got 0.171 sec with same code :) GCC suxx. Dunno if it's input or sorting or what. I was using scanf/printf (cin/cout are slower in VisualC even with iostream::sync_with_stdio(false)).

Here is the solutuion
http://xoptutorials.com/index.php/2017/01/01/timus1926/

I've got absolutely the same problem. I use suffix and lcp arrays.

I use the following algo:
for i = 1 to LENGTH_OF_ALL_WORDS
  l = the closest preceding suffix that belong to another word
  r = the closest succeeding suffix that belong to another word
  v = max(lcp(l, i), lcp(i, r)) + 1;
  w = the word that contains suffix i;
  if (v < ans[w]) ans[w] = v;

I've tried lots of tests but can't find what's wrong.

Try this

2
mississipi
misisspi

Consider that for any vectors a,b,c, |a|,|b|,|c| <= L exists integers u, v, w, |u|,|v|,|w|=1, |ua+vb+wc|<=L

Your algo should be O(n) ;)
I don't quite understand how write it with complexity of O(n log n)

Matrix should not overlap itself after 90-degree rotations (no two '1' at same position) and should cover all NxN elements after 4 such rotations.

O(N^4) simple algo exists.

Given advices too weak to be helpfull.
For me key idea was forming n*n/4 classes with 4 cell in each and working
with level, where 1<=level<=n*n;
We counting all combinations under level in each classes exept whose are used already.

And also not using G constant :)

Yes, there is after preliminary DP for min-price-allowed-steps-graph.

There is 30000*100 solution O(filling X dishes)

хз

Never

Edited by author 08.08.2022 11:27

6 6
1 2 1
2 3 2
3 1 3
4 5 1
5 6 2
6 4 3

Yes, there are exists one very beautiful O(N^2) solution. But the practical complexity of this algo is much less :)

could you describe your solution? my algo O(logn * l^3 * t) has TL(
i try to find solution like this: dp[i, a, l] , i is bit number, a is addition to i-bit, l is lost count

Yes, there is. (L^2)*log(N) solution (0.187 sec). I DP on total amount of coins and amount of extra coins for next denomination (the latter is used to know how much more can I push forward when I advance a digit). The first index always increases by K-1, the second always increases by K, so it's kind of diagonal partial summing up matrix to itself. If you precalculate reachable sums properly, you can perform DP transfer in O(L^2).