oj.uz

Submission #940671

# Submission time Handle Problem Language Result Execution time Memory
940671 2024-03-07T13:03:23 Z vjudge1 Wombats (IOI13_wombats) C++17
100 / 100
 7564 ms 177780 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 341 ms 170612 KB Output is correct
2 Correct 334 ms 170604 KB Output is correct
3 Correct 359 ms 172372 KB Output is correct
4 Correct 322 ms 170380 KB Output is correct
5 Correct 321 ms 170376 KB Output is correct
6 Correct 31 ms 160592 KB Output is correct
7 Correct 31 ms 160596 KB Output is correct
8 Correct 36 ms 160484 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 160592 KB Output is correct
2 Correct 33 ms 160820 KB Output is correct
3 Correct 31 ms 160596 KB Output is correct
4 Correct 32 ms 164700 KB Output is correct
5 Correct 31 ms 164692 KB Output is correct
6 Correct 33 ms 164688 KB Output is correct
7 Correct 33 ms 164688 KB Output is correct
8 Correct 31 ms 164560 KB Output is correct
9 Correct 32 ms 164692 KB Output is correct
10 Correct 32 ms 164612 KB Output is correct
11 Correct 87 ms 165720 KB Output is correct
12 Correct 32 ms 164688 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 165716 KB Output is correct
2 Correct 289 ms 165384 KB Output is correct
3 Correct 294 ms 165604 KB Output is correct
4 Correct 306 ms 165600 KB Output is correct
5 Correct 297 ms 165460 KB Output is correct
6 Correct 34 ms 160448 KB Output is correct
7 Correct 33 ms 160600 KB Output is correct
8 Correct 34 ms 160524 KB Output is correct
9 Correct 1339 ms 165604 KB Output is correct
10 Correct 36 ms 164688 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 176148 KB Output is correct
2 Correct 301 ms 175964 KB Output is correct
3 Correct 334 ms 175952 KB Output is correct
4 Correct 337 ms 176760 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 165600 KB Output is correct
2 Correct 305 ms 165608 KB Output is correct
3 Correct 303 ms 165604 KB Output is correct
4 Correct 291 ms 165604 KB Output is correct
5 Correct 300 ms 165460 KB Output is correct
6 Correct 308 ms 176208 KB Output is correct
7 Correct 332 ms 176164 KB Output is correct
8 Correct 333 ms 176208 KB Output is correct
9 Correct 335 ms 176920 KB Output is correct
10 Correct 304 ms 170604 KB Output is correct
11 Correct 304 ms 170604 KB Output is correct
12 Correct 349 ms 172136 KB Output is correct
13 Correct 335 ms 170580 KB Output is correct
14 Correct 304 ms 170836 KB Output is correct
15 Correct 33 ms 160396 KB Output is correct
16 Correct 32 ms 160592 KB Output is correct
17 Correct 32 ms 160596 KB Output is correct
18 Correct 33 ms 164692 KB Output is correct
19 Correct 36 ms 164696 KB Output is correct
20 Correct 32 ms 164716 KB Output is correct
21 Correct 38 ms 164512 KB Output is correct
22 Correct 32 ms 164708 KB Output is correct
23 Correct 33 ms 164688 KB Output is correct
24 Correct 32 ms 164604 KB Output is correct
25 Correct 89 ms 165640 KB Output is correct
26 Correct 40 ms 164736 KB Output is correct
27 Correct 1321 ms 165612 KB Output is correct
28 Correct 2088 ms 176464 KB Output is correct
29 Correct 2068 ms 175692 KB Output is correct
30 Correct 2109 ms 175988 KB Output is correct
31 Correct 2111 ms 177444 KB Output is correct
32 Correct 32 ms 164588 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 165604 KB Output is correct
2 Correct 286 ms 165604 KB Output is correct
3 Correct 304 ms 165708 KB Output is correct
4 Correct 295 ms 165600 KB Output is correct
5 Correct 298 ms 165460 KB Output is correct
6 Correct 312 ms 176152 KB Output is correct
7 Correct 299 ms 176148 KB Output is correct
8 Correct 332 ms 175908 KB Output is correct
9 Correct 355 ms 176944 KB Output is correct
10 Correct 323 ms 170600 KB Output is correct
11 Correct 298 ms 170580 KB Output is correct
12 Correct 371 ms 172328 KB Output is correct
13 Correct 331 ms 170832 KB Output is correct
14 Correct 299 ms 170580 KB Output is correct
15 Correct 1349 ms 176356 KB Output is correct
16 Correct 7546 ms 177736 KB Output is correct
17 Correct 32 ms 160604 KB Output is correct
18 Correct 31 ms 160596 KB Output is correct
19 Correct 32 ms 160644 KB Output is correct
20 Correct 32 ms 164668 KB Output is correct
21 Correct 33 ms 164692 KB Output is correct
22 Correct 32 ms 164692 KB Output is correct
23 Correct 33 ms 164700 KB Output is correct
24 Correct 33 ms 164612 KB Output is correct
25 Correct 32 ms 164560 KB Output is correct
26 Correct 40 ms 164692 KB Output is correct
27 Correct 92 ms 165716 KB Output is correct
28 Correct 33 ms 164728 KB Output is correct
29 Correct 1333 ms 165604 KB Output is correct
30 Correct 2044 ms 176592 KB Output is correct
31 Correct 7156 ms 176656 KB Output is correct
32 Correct 7261 ms 177060 KB Output is correct
33 Correct 2071 ms 176004 KB Output is correct
34 Correct 7211 ms 176096 KB Output is correct
35 Correct 2082 ms 175976 KB Output is correct
36 Correct 7331 ms 176544 KB Output is correct
37 Correct 2097 ms 177428 KB Output is correct
38 Correct 7276 ms 177780 KB Output is correct
39 Correct 32 ms 164688 KB Output is correct
40 Correct 7564 ms 176620 KB Output is correct