| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
I guess it's a compiler optimization
In your code if $$$g[i][j]$$$ is false, it won't do anything in the loop.
I guess GCC adds
if (!g[i][j]) break;to the end of line 19Great, but this condition will never happen if the entire grid = 1
You're right, it might be because of random-access and you are defining vectors inside the function (i.e. heap/stack thing).
But I don't think so because I resubmitted with defining in global and no difference.
Thanks for your time, I think now you are curious too :D
Second code gets TLE'd because of some cache shenanigans.
My thoughts that CPU in first submit prefetches full cache line, so access to $$$newdp[mask]$$$ is almost free, but in the other submit, it can be washed out by accessing $$$g[i][j]$$$.
And AFAIK, arrays with len that are powers of two are quite bad for performance reasons on some CPUs, see this link for reference.
I thought that cache stuff don't affect complexity that much.
Now I got it thanks :D
Technically you're right. It doesn't affect the complexity at all. It does affect the constant factor though, which is what's causing the 2.5x speedup here.
No words come after yours sir.
similar thing has happened with me once on cf. i think it is due to more cache miss rate in second one but can't guess why it's happening