ZERO111's blog

I've wrote the same code a the tutorial but it getting TLE
By ZERO111, history, 7 months ago, In English

here is the submission 370310085

here is the tutorial code 370309621

please, help

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I'm not sure if that's the actual issue but I'm pretty sure __gcd isn't O(1) and it's actually logarithmic which means inside of that triple loop you're calling __gcd millions of times.

I'd say you just need to optimize this but I'm not 100% sure.

Also using vector<vector> dp(n, vector(l, -1e18)) inside of while (t--) might be memory risky

→ Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

the problem is the gcd probably,__gcd and gcd uses different algorithms, I dont know what algortihm __gcd uses but gcd use Euclidean algorithm which is faster

→ Reply