oj.uz

Submission #290491

# Submission time Handle Problem Language Result Execution time Memory
290491 2020-09-03T22:08:13 Z fivefourthreeone Wombats (IOI13_wombats) C++17
100 / 100
 4756 ms 183672 KB 
#include "wombats.h"
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxR = 5000;
const int mxC = 200;
const int BLOCK = 10;
const int sgsz = 500;
int h[mxR][mxC], v[mxR][mxC], seg[1024][mxC][mxC], opt[mxC + 1];
void upd(int l, int r, int le = 0, int rr = sgsz-1, int i = 1) {
    if(le > r||rr < l)return;
    if(le==rr) {
        //brute force this BLOCK
        memset(seg[i], INF, sizeof(seg[i]));
        owo(j, 0, mxC) {
            seg[i][j][j] = 0;
            owo(k, le*BLOCK, le*BLOCK + BLOCK) {
                owo(b, 1, mxC) {
                    seg[i][j][b] = min(seg[i][j][b], seg[i][j][b-1] + h[k][b-1]);
                }
                uwu(b, mxC, 1) {
                    seg[i][j][b-1] = min(seg[i][j][b-1], seg[i][j][b] + h[k][b-1]);
                }
                owo(b, 0, mxC) {
                    seg[i][j][b] += v[k][b];
                }
            }
        }
        return;
    }
    int mid = (le + rr) >> 1;
    upd(l, r, le, mid, 2*i);
    upd(l, r, mid+1, rr, 2*i+1);
    memset(opt, 0, 4*mxC);
    owo(j, 0, mxC) {
        for(int k = mxC - 1; ~k; --k) {
            ttgl best = {INF, 0};
            owo(b, opt[k], opt[k+1] + 1) {
                best = min(best, {seg[2*i][j][b] + seg[2*i+1][b][k], -b});
            }
            seg[i][j][k] = best.first;
            opt[k] = -best.second;
        }
    }
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
    memset(h, INF, sizeof(h));
    owo(i, 0, r) {
        owo(j, 0, c-1) {
            h[i][j] = H[i][j];
        }
    }
    owo(i, 0, r-1) {
        owo(j, 0, c) {
            v[i][j] = V[i][j];
        }
    }
    opt[mxC] = mxC-1;
    upd(0, sgsz-1);
}
void changeH(int p, int q, int w) {
    h[p][q] = w;
    upd(p/BLOCK, p/BLOCK);
}
void changeV(int p, int q, int w) {
    v[p][q] = w;
    upd(p/BLOCK, p/BLOCK);
}
int escape(int a, int b) {
    return seg[1][a][b];
}
/*int hh[5000][200];
int vv[5000][200];
int main() {
    freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    int r, c;
    int q;
    cin>>r>>c;
    owo(i, 0, r) {
        owo(j, 0, c-1) {
            cin>>hh[i][j];
        }
    }
    owo(i, 0, r-1) {
        owo(j, 0, c) {
            cin>>vv[i][j];
        }
    }
    int type;
    init(r, c, hh, vv);
    cin>>q;
    int x, y, z;
    while(q--) {
        cin>>type;
        if(type==1) {
            cin>>x>>y>>z;
            changeH(x, y, z);
        }else if(type==2) {
            cin>>x>>y>>z;
            changeV(x, y, z);
        }else {
            cin>>x>>y;
            cout<<escape(x, y)<<"\n";
        }
    }
    return 0;
}*/

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
wombats.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4319 ms 168776 KB Output is correct
2 Correct 4340 ms 168792 KB Output is correct
3 Correct 4423 ms 171500 KB Output is correct
4 Correct 4388 ms 168800 KB Output is correct
5 Correct 4352 ms 168912 KB Output is correct
6 Correct 1510 ms 161016 KB Output is correct
7 Correct 1513 ms 160888 KB Output is correct
8 Correct 1495 ms 160844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1510 ms 160780 KB Output is correct
2 Correct 1515 ms 160888 KB Output is correct
3 Correct 1507 ms 160800 KB Output is correct
4 Correct 1494 ms 160944 KB Output is correct
5 Correct 1495 ms 160824 KB Output is correct
6 Correct 1514 ms 160960 KB Output is correct
7 Correct 1510 ms 160808 KB Output is correct
8 Correct 1504 ms 160912 KB Output is correct
9 Correct 1501 ms 160780 KB Output is correct
10 Correct 1507 ms 160884 KB Output is correct
11 Correct 1586 ms 163192 KB Output is correct
12 Correct 1500 ms 161032 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2066 ms 161144 KB Output is correct
2 Correct 2058 ms 161196 KB Output is correct
3 Correct 2079 ms 161144 KB Output is correct
4 Correct 2085 ms 161144 KB Output is correct
5 Correct 2066 ms 161272 KB Output is correct
6 Correct 1499 ms 160900 KB Output is correct
7 Correct 1507 ms 160828 KB Output is correct
8 Correct 1508 ms 160888 KB Output is correct
9 Correct 4286 ms 161272 KB Output is correct
10 Correct 1518 ms 161040 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4330 ms 172576 KB Output is correct
2 Correct 4340 ms 172988 KB Output is correct
3 Correct 4362 ms 172764 KB Output is correct
4 Correct 4371 ms 174124 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2055 ms 161036 KB Output is correct
2 Correct 2067 ms 161268 KB Output is correct
3 Correct 2067 ms 161404 KB Output is correct
4 Correct 2083 ms 161192 KB Output is correct
5 Correct 2086 ms 161272 KB Output is correct
6 Correct 4327 ms 172796 KB Output is correct
7 Correct 4385 ms 172748 KB Output is correct
8 Correct 4391 ms 172764 KB Output is correct
9 Correct 4425 ms 174224 KB Output is correct
10 Correct 4301 ms 168696 KB Output is correct
11 Correct 4366 ms 168644 KB Output is correct
12 Correct 4421 ms 171464 KB Output is correct
13 Correct 4430 ms 168660 KB Output is correct
14 Correct 4362 ms 168608 KB Output is correct
15 Correct 1508 ms 160704 KB Output is correct
16 Correct 1517 ms 160808 KB Output is correct
17 Correct 1501 ms 160892 KB Output is correct
18 Correct 1495 ms 160756 KB Output is correct
19 Correct 1491 ms 160816 KB Output is correct
20 Correct 1500 ms 160888 KB Output is correct
21 Correct 1498 ms 160888 KB Output is correct
22 Correct 1494 ms 160888 KB Output is correct
23 Correct 1492 ms 160888 KB Output is correct
24 Correct 1490 ms 160888 KB Output is correct
25 Correct 1583 ms 163120 KB Output is correct
26 Correct 1499 ms 160936 KB Output is correct
27 Correct 4274 ms 161208 KB Output is correct
28 Correct 4463 ms 176948 KB Output is correct
29 Correct 4510 ms 174328 KB Output is correct
30 Correct 4535 ms 174400 KB Output is correct
31 Correct 4541 ms 178812 KB Output is correct
32 Correct 1507 ms 160808 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2059 ms 161180 KB Output is correct
2 Correct 2054 ms 161164 KB Output is correct
3 Correct 2068 ms 161264 KB Output is correct
4 Correct 2077 ms 161268 KB Output is correct
5 Correct 2093 ms 160972 KB Output is correct
6 Correct 4331 ms 172788 KB Output is correct
7 Correct 4356 ms 172792 KB Output is correct
8 Correct 4378 ms 172824 KB Output is correct
9 Correct 4391 ms 174100 KB Output is correct
10 Correct 4280 ms 168568 KB Output is correct
11 Correct 4324 ms 168736 KB Output is correct
12 Correct 4437 ms 171404 KB Output is correct
13 Correct 4363 ms 168804 KB Output is correct
14 Correct 4356 ms 168696 KB Output is correct
15 Correct 1761 ms 182348 KB Output is correct
16 Correct 4663 ms 183672 KB Output is correct
17 Correct 1503 ms 160744 KB Output is correct
18 Correct 1501 ms 160888 KB Output is correct
19 Correct 1498 ms 160800 KB Output is correct
20 Correct 1494 ms 160776 KB Output is correct
21 Correct 1501 ms 160888 KB Output is correct
22 Correct 1492 ms 160868 KB Output is correct
23 Correct 1498 ms 160904 KB Output is correct
24 Correct 1501 ms 161008 KB Output is correct
25 Correct 1523 ms 160928 KB Output is correct
26 Correct 1502 ms 161016 KB Output is correct
27 Correct 1579 ms 163320 KB Output is correct
28 Correct 1491 ms 160760 KB Output is correct
29 Correct 4275 ms 161272 KB Output is correct
30 Correct 4452 ms 176596 KB Output is correct
31 Correct 4286 ms 181304 KB Output is correct
32 Correct 4302 ms 180992 KB Output is correct
33 Correct 4490 ms 174260 KB Output is correct
34 Correct 4546 ms 178328 KB Output is correct
35 Correct 4504 ms 174212 KB Output is correct
36 Correct 4633 ms 178068 KB Output is correct
37 Correct 4531 ms 178448 KB Output is correct
38 Correct 4422 ms 181396 KB Output is correct
39 Correct 1504 ms 160840 KB Output is correct
40 Correct 4756 ms 178332 KB Output is correct