oj.uz

Submission #940659

# Submission time Handle Problem Language Result Execution time Memory
940659 2024-03-07T12:47:57 Z shenfe1 Wombats (IOI13_wombats) C++17
76 / 100
 11964 ms 196924 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=0;k<m;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")
      | 
wombats.cpp: In function 'node mrg(node, node)':
wombats.cpp:73:11: warning: unused variable 'l' [-Wunused-variable]
   73 |       int l=(i-1>=0?opt[i-1][j]:0);
      |           ^
wombats.cpp:74:11: warning: unused variable 'r' [-Wunused-variable]
   74 |       int r=opt[i][j+1];
      |           ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 89176 KB Output is correct
2 Correct 93 ms 89344 KB Output is correct
3 Correct 145 ms 91984 KB Output is correct
4 Correct 97 ms 89348 KB Output is correct
5 Correct 95 ms 89344 KB Output is correct
6 Correct 17 ms 82380 KB Output is correct
7 Correct 17 ms 82524 KB Output is correct
8 Correct 17 ms 82524 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 82520 KB Output is correct
3 Correct 17 ms 82776 KB Output is correct
4 Correct 18 ms 86620 KB Output is correct
5 Correct 17 ms 86620 KB Output is correct
6 Correct 18 ms 86572 KB Output is correct
7 Correct 18 ms 86620 KB Output is correct
8 Correct 18 ms 86872 KB Output is correct
9 Correct 17 ms 86808 KB Output is correct
10 Correct 18 ms 86620 KB Output is correct
11 Correct 72 ms 89072 KB Output is correct
12 Correct 17 ms 86620 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 87220 KB Output is correct
2 Correct 905 ms 87032 KB Output is correct
3 Correct 1008 ms 87052 KB Output is correct
4 Correct 1026 ms 87044 KB Output is correct
5 Correct 1054 ms 87040 KB Output is correct
6 Correct 17 ms 82520 KB Output is correct
7 Correct 21 ms 82524 KB Output is correct
8 Correct 18 ms 82512 KB Output is correct
9 Correct 4542 ms 87040 KB Output is correct
10 Correct 17 ms 86620 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 92588 KB Output is correct
2 Correct 95 ms 92496 KB Output is correct
3 Correct 98 ms 92660 KB Output is correct
4 Correct 122 ms 93836 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 86800 KB Output is correct
2 Correct 892 ms 87116 KB Output is correct
3 Correct 1010 ms 87044 KB Output is correct
4 Correct 989 ms 87120 KB Output is correct
5 Correct 1057 ms 87052 KB Output is correct
6 Correct 95 ms 92664 KB Output is correct
7 Correct 94 ms 92496 KB Output is correct
8 Correct 115 ms 92756 KB Output is correct
9 Correct 125 ms 94032 KB Output is correct
10 Correct 91 ms 89176 KB Output is correct
11 Correct 123 ms 89172 KB Output is correct
12 Correct 146 ms 91952 KB Output is correct
13 Correct 98 ms 89432 KB Output is correct
14 Correct 95 ms 89348 KB Output is correct
15 Correct 17 ms 82444 KB Output is correct
16 Correct 16 ms 82524 KB Output is correct
17 Correct 16 ms 82524 KB Output is correct
18 Correct 17 ms 86616 KB Output is correct
19 Correct 18 ms 86620 KB Output is correct
20 Correct 18 ms 86716 KB Output is correct
21 Correct 17 ms 86620 KB Output is correct
22 Correct 17 ms 86620 KB Output is correct
23 Correct 17 ms 86620 KB Output is correct
24 Correct 18 ms 86620 KB Output is correct
25 Correct 73 ms 89120 KB Output is correct
26 Correct 18 ms 86616 KB Output is correct
27 Correct 4618 ms 87108 KB Output is correct
28 Correct 11452 ms 97160 KB Output is correct
29 Correct 11964 ms 96676 KB Output is correct
30 Correct 11962 ms 96552 KB Output is correct
31 Correct 11479 ms 98424 KB Output is correct
32 Correct 39 ms 86612 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 86876 KB Output is correct
2 Correct 902 ms 87028 KB Output is correct
3 Correct 1014 ms 87140 KB Output is correct
4 Correct 982 ms 86956 KB Output is correct
5 Correct 1077 ms 87044 KB Output is correct
6 Correct 116 ms 92660 KB Output is correct
7 Correct 96 ms 92508 KB Output is correct
8 Correct 101 ms 92660 KB Output is correct
9 Correct 124 ms 93956 KB Output is correct
10 Correct 94 ms 89332 KB Output is correct
11 Correct 93 ms 89176 KB Output is correct
12 Correct 148 ms 92052 KB Output is correct
13 Correct 111 ms 89428 KB Output is correct
14 Correct 95 ms 89336 KB Output is correct
15 Runtime error 222 ms 196924 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -