oj.uz

Submission #940667

# Submission time Handle Problem Language Result Execution time Memory
940667 2024-03-07T12:55:37 Z shenfe1 Wombats (IOI13_wombats) C++17
100 / 100
 7549 ms 187456 KB 
#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")
#pragma oprimize("unroll-loops")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll

const int MAX=201;
const ll inf=1e9;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1);
  int k=binpow(a,n/2);
  return k*k;
}

#include "wombats.h"

int A[5001][MAX];
int B[5001][MAX];
int n,m;

struct node{
  int d[MAX][MAX];
  int l,r;
  node(){
    for(int i=0;i<MAX;i++){
      for(int j=0;j<MAX;j++){
        d[i][j]=inf;
      }
    }
  }
}t[1001];

const int QQ=20;

node mrg(node a,node b){
  node res;
  res.l=a.l;
  res.r=b.r;
  int opt[MAX][MAX];
  mem(opt,0);
  for(int i=0;i<=m;i++){
    opt[i][m]=m-1;
  }
  for(int i=0;i<m;i++){
    for(int j=m-1;j>=0;j--){
      res.d[i][j]=inf;
      int l=(i-1>=0?opt[i-1][j]:0);
      int r=opt[i][j+1];
      for(int k=l;k<=r;k++){
        if(b.d[i][k]+a.d[k][j]<res.d[i][j]){
          res.d[i][j]=b.d[i][k]+a.d[k][j];
          opt[i][j]=k;
        }
      }
    }
  }
  return res;
}

void build(int v,int tl,int tr){
  if(tl==tr){
    t[v].l=tl*QQ;
    t[v].r=(tl+1)*QQ;
    t[v].r=min(t[v].r,n-1);
    for(int i=0;i<m;i++){
      vector<int> prv(m);
      prv[i]=0;
      for(int j=i+1;j<m;j++)prv[j]=prv[j-1]+A[t[v].r][j-1];
      for(int j=i-1;j>=0;j--)prv[j]=prv[j+1]+A[t[v].r][j];
      for(int j=t[v].r-1;j>=t[v].l;j--){
        int pmn[MAX];
        int smn[MAX];
        pmn[0]=prv[0]+B[j][0];
        for(int k=1;k<m;k++){
          pmn[k]=min(pmn[k-1]+A[j][k-1],prv[k]+B[j][k]);
        }
        smn[m-1]=prv[m-1]+B[j][m-1];
        for(int k=m-2;k>=0;k--){
          smn[k]=min(smn[k+1]+A[j][k],prv[k]+B[j][k]);
        }
        for(int k=0;k<m;k++){
          prv[k]=min(smn[k],pmn[k]);
        }
        // cout<<i<<" "<<j<<"\n";
        // for(int j=0;j<m;j++)cout<<prv[j]<<" ";
        // cout<<"\n";
      }
      for(int j=0;j<m;j++){
        t[v].d[i][j]=prv[j];
      }
    }
    return;
  }
  int tm=(tl+tr)/2;
  build(2*v,tl,tm);
  build(2*v+1,tm+1,tr);
  // cout<<"???\n";
  t[v]=mrg(t[2*v],t[2*v+1]);
}

void update(int v,int tl,int tr,int pos){
  if(tl==tr){
    t[v].l=tl*QQ;
    t[v].r=(tl+1)*QQ;
    t[v].r=min(t[v].r,n-1);
    // cout<<t[v].l<<" "<<t[v].r<<"\n";
    for(int i=0;i<m;i++){
      vector<int> prv(m);
      prv[i]=0;
      for(int j=i+1;j<m;j++)prv[j]=prv[j-1]+A[t[v].r][j-1];
      for(int j=i-1;j>=0;j--)prv[j]=prv[j+1]+A[t[v].r][j];
      for(int j=t[v].r-1;j>=t[v].l;j--){
        int pmn[MAX];
        int smn[MAX];
        pmn[0]=prv[0]+B[j][0];
        for(int k=1;k<m;k++){
          pmn[k]=min(pmn[k-1]+A[j][k-1],prv[k]+B[j][k]);
        }
        smn[m-1]=prv[m-1]+B[j][m-1];
        for(int k=m-2;k>=0;k--){
          smn[k]=min(smn[k+1]+A[j][k],prv[k]+B[j][k]);
        }
        for(int k=0;k<m;k++){
          prv[k]=min(smn[k],pmn[k]);
        }
        // cout<<i<<" "<<j<<"\n";
        // for(int j=0;j<m;j++)cout<<prv[j]<<" ";
        // cout<<"\n";
      }
      for(int j=0;j<m;j++){
        t[v].d[i][j]=prv[j];
      }
    }
    return;
  }
  int tm=(tl+tr)/2;
  if(pos<=tm)update(2*v,tl,tm,pos);
  else update(2*v+1,tm+1,tr,pos);
// cout<<"???\n";
  t[v]=mrg(t[2*v],t[2*v+1]);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  n=R;
  m=C;
  for(int i=0;i<R;i++){
    for(int j=0;j<C-1;j++){
      A[i][j]=H[i][j];
    }
  }
  for(int i=0;i<R-1;i++){
    for(int j=0;j<C;j++){
      B[i][j]=V[i][j];
    }
  }
  // cout<<(n+9)/10-1<<"\n";
  build(1,0,(n+QQ-1)/QQ-1);
}

void changeH(int P, int Q, int W) {
  A[P][Q]=W;
  update(1,0,(n+QQ-1)/QQ-1,(P-1)/QQ);
  update(1,0,(n+QQ-1)/QQ-1,P/QQ);
}

void changeV(int P, int Q, int W) {
  B[P][Q]=W;
  update(1,0,(n+QQ-1)/QQ-1,(P-1)/QQ);
  update(1,0,(n+QQ-1)/QQ-1,P/QQ);  
}

int escape(int V1, int V2) {
  return t[1].d[V2][V1];
}

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 optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
wombats.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      | 
wombats.cpp:5: warning: ignoring '#pragma oprimize ' [-Wunknown-pragmas]
    5 | #pragma oprimize("unroll-loops")
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 170576 KB Output is correct
2 Correct 304 ms 170604 KB Output is correct
3 Correct 370 ms 172188 KB Output is correct
4 Correct 317 ms 170580 KB Output is correct
5 Correct 303 ms 170604 KB Output is correct
6 Correct 31 ms 160596 KB Output is correct
7 Correct 32 ms 160448 KB Output is correct
8 Correct 32 ms 160612 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 160600 KB Output is correct
2 Correct 32 ms 160596 KB Output is correct
3 Correct 34 ms 160604 KB Output is correct
4 Correct 37 ms 164520 KB Output is correct
5 Correct 33 ms 164608 KB Output is correct
6 Correct 40 ms 164692 KB Output is correct
7 Correct 33 ms 164692 KB Output is correct
8 Correct 32 ms 164620 KB Output is correct
9 Correct 32 ms 164688 KB Output is correct
10 Correct 33 ms 164688 KB Output is correct
11 Correct 88 ms 165700 KB Output is correct
12 Correct 33 ms 164700 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 165608 KB Output is correct
2 Correct 294 ms 165604 KB Output is correct
3 Correct 292 ms 165460 KB Output is correct
4 Correct 289 ms 165716 KB Output is correct
5 Correct 298 ms 165608 KB Output is correct
6 Correct 36 ms 160592 KB Output is correct
7 Correct 32 ms 160596 KB Output is correct
8 Correct 43 ms 160588 KB Output is correct
9 Correct 1311 ms 165608 KB Output is correct
10 Correct 32 ms 164700 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 176240 KB Output is correct
2 Correct 294 ms 176148 KB Output is correct
3 Correct 328 ms 175956 KB Output is correct
4 Correct 339 ms 176724 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 165712 KB Output is correct
2 Correct 286 ms 165460 KB Output is correct
3 Correct 304 ms 165712 KB Output is correct
4 Correct 291 ms 165612 KB Output is correct
5 Correct 296 ms 165456 KB Output is correct
6 Correct 308 ms 176152 KB Output is correct
7 Correct 305 ms 175960 KB Output is correct
8 Correct 350 ms 175956 KB Output is correct
9 Correct 354 ms 176976 KB Output is correct
10 Correct 310 ms 170836 KB Output is correct
11 Correct 300 ms 170364 KB Output is correct
12 Correct 360 ms 172116 KB Output is correct
13 Correct 326 ms 170580 KB Output is correct
14 Correct 312 ms 170832 KB Output is correct
15 Correct 31 ms 160592 KB Output is correct
16 Correct 33 ms 160380 KB Output is correct
17 Correct 32 ms 160616 KB Output is correct
18 Correct 33 ms 164692 KB Output is correct
19 Correct 35 ms 164688 KB Output is correct
20 Correct 33 ms 164692 KB Output is correct
21 Correct 32 ms 164692 KB Output is correct
22 Correct 33 ms 164692 KB Output is correct
23 Correct 32 ms 164700 KB Output is correct
24 Correct 33 ms 164700 KB Output is correct
25 Correct 107 ms 165720 KB Output is correct
26 Correct 32 ms 164688 KB Output is correct
27 Correct 1326 ms 165988 KB Output is correct
28 Correct 2069 ms 176512 KB Output is correct
29 Correct 2032 ms 175636 KB Output is correct
30 Correct 2066 ms 175724 KB Output is correct
31 Correct 2128 ms 177492 KB Output is correct
32 Correct 41 ms 164596 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 165608 KB Output is correct
2 Correct 288 ms 165600 KB Output is correct
3 Correct 296 ms 165456 KB Output is correct
4 Correct 294 ms 165460 KB Output is correct
5 Correct 307 ms 165852 KB Output is correct
6 Correct 300 ms 176212 KB Output is correct
7 Correct 308 ms 176400 KB Output is correct
8 Correct 327 ms 176156 KB Output is correct
9 Correct 345 ms 176724 KB Output is correct
10 Correct 306 ms 170860 KB Output is correct
11 Correct 309 ms 170612 KB Output is correct
12 Correct 354 ms 172664 KB Output is correct
13 Correct 328 ms 170604 KB Output is correct
14 Correct 303 ms 170604 KB Output is correct
15 Correct 1346 ms 176156 KB Output is correct
16 Correct 7549 ms 187456 KB Output is correct
17 Correct 32 ms 160592 KB Output is correct
18 Correct 31 ms 160596 KB Output is correct
19 Correct 32 ms 160592 KB Output is correct
20 Correct 33 ms 164688 KB Output is correct
21 Correct 33 ms 164768 KB Output is correct
22 Correct 33 ms 164692 KB Output is correct
23 Correct 33 ms 164952 KB Output is correct
24 Correct 32 ms 164604 KB Output is correct
25 Correct 32 ms 164716 KB Output is correct
26 Correct 34 ms 164692 KB Output is correct
27 Correct 88 ms 166996 KB Output is correct
28 Correct 33 ms 164692 KB Output is correct
29 Correct 1325 ms 165868 KB Output is correct
30 Correct 2055 ms 180640 KB Output is correct
31 Correct 7282 ms 184708 KB Output is correct
32 Correct 7362 ms 184880 KB Output is correct
33 Correct 2037 ms 179436 KB Output is correct
34 Correct 7277 ms 184036 KB Output is correct
35 Correct 2092 ms 179564 KB Output is correct
36 Correct 7307 ms 183240 KB Output is correct
37 Correct 2075 ms 182104 KB Output is correct
38 Correct 7205 ms 185288 KB Output is correct
39 Correct 32 ms 164700 KB Output is correct
40 Correct 7517 ms 183400 KB Output is correct