oj.uz

Submission #940662

# Submission time Handle Problem Language Result Execution time Memory
940662 2024-03-07T12:49:55 Z shenfe1 Wombats (IOI13_wombats) C++17
76 / 100
 1483 ms 187224 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=101;
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[2001];

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*10;
    t[v].r=(tl+1)*10;
    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*10;
    t[v].r=(tl+1)*10;
    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+9)/10-1);
}

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

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

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 106 ms 89316 KB Output is correct
2 Correct 98 ms 89292 KB Output is correct
3 Correct 148 ms 90868 KB Output is correct
4 Correct 97 ms 89180 KB Output is correct
5 Correct 96 ms 89176 KB Output is correct
6 Correct 17 ms 82520 KB Output is correct
7 Correct 17 ms 82524 KB Output is correct
8 Correct 17 ms 82500 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 82524 KB Output is correct
2 Correct 17 ms 82524 KB Output is correct
3 Correct 16 ms 82520 KB Output is correct
4 Correct 18 ms 86620 KB Output is correct
5 Correct 20 ms 86996 KB Output is correct
6 Correct 17 ms 86616 KB Output is correct
7 Correct 18 ms 86620 KB Output is correct
8 Correct 17 ms 86620 KB Output is correct
9 Correct 17 ms 86620 KB Output is correct
10 Correct 18 ms 86740 KB Output is correct
11 Correct 74 ms 87744 KB Output is correct
12 Correct 17 ms 86540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 86960 KB Output is correct
2 Correct 168 ms 86980 KB Output is correct
3 Correct 181 ms 86876 KB Output is correct
4 Correct 184 ms 86984 KB Output is correct
5 Correct 180 ms 87124 KB Output is correct
6 Correct 18 ms 82432 KB Output is correct
7 Correct 18 ms 82560 KB Output is correct
8 Correct 17 ms 82524 KB Output is correct
9 Correct 765 ms 86964 KB Output is correct
10 Correct 20 ms 86616 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 92588 KB Output is correct
2 Correct 96 ms 92588 KB Output is correct
3 Correct 100 ms 92592 KB Output is correct
4 Correct 123 ms 93268 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 87080 KB Output is correct
2 Correct 163 ms 86876 KB Output is correct
3 Correct 178 ms 86872 KB Output is correct
4 Correct 177 ms 86964 KB Output is correct
5 Correct 178 ms 86964 KB Output is correct
6 Correct 95 ms 92592 KB Output is correct
7 Correct 95 ms 92508 KB Output is correct
8 Correct 104 ms 92588 KB Output is correct
9 Correct 133 ms 93500 KB Output is correct
10 Correct 93 ms 89180 KB Output is correct
11 Correct 99 ms 89316 KB Output is correct
12 Correct 148 ms 90852 KB Output is correct
13 Correct 98 ms 89312 KB Output is correct
14 Correct 93 ms 89180 KB Output is correct
15 Correct 16 ms 82524 KB Output is correct
16 Correct 17 ms 82512 KB Output is correct
17 Correct 18 ms 82720 KB Output is correct
18 Correct 18 ms 86608 KB Output is correct
19 Correct 18 ms 86620 KB Output is correct
20 Correct 18 ms 86536 KB Output is correct
21 Correct 17 ms 86616 KB Output is correct
22 Correct 18 ms 86620 KB Output is correct
23 Correct 18 ms 86732 KB Output is correct
24 Correct 17 ms 86616 KB Output is correct
25 Correct 76 ms 87696 KB Output is correct
26 Correct 17 ms 86616 KB Output is correct
27 Correct 770 ms 86960 KB Output is correct
28 Correct 1464 ms 93112 KB Output is correct
29 Correct 1439 ms 92628 KB Output is correct
30 Correct 1483 ms 92560 KB Output is correct
31 Correct 1414 ms 93928 KB Output is correct
32 Correct 17 ms 86620 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 86964 KB Output is correct
2 Correct 166 ms 86964 KB Output is correct
3 Correct 182 ms 86872 KB Output is correct
4 Correct 186 ms 86960 KB Output is correct
5 Correct 176 ms 86872 KB Output is correct
6 Correct 97 ms 92508 KB Output is correct
7 Correct 103 ms 92508 KB Output is correct
8 Correct 101 ms 92508 KB Output is correct
9 Correct 126 ms 93264 KB Output is correct
10 Correct 94 ms 89180 KB Output is correct
11 Correct 92 ms 89180 KB Output is correct
12 Correct 149 ms 90704 KB Output is correct
13 Correct 117 ms 89316 KB Output is correct
14 Correct 94 ms 89176 KB Output is correct
15 Runtime error 235 ms 187224 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -