Submission #428700

#	Time	Username	Problem	Language	Result	Execution time	Memory
428700		rumen_m	Wombats (IOI13_wombats)	C++17	12 / 100	550 ms	16212 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxc = 205;
const int maxr = 5005;
const int group = 30;
const int inf = 1e9;
int segm[(1<<10)+42][maxc][maxc];
int h[maxr][maxc],v[maxr][maxc];
int r,c;
int curr[maxc][maxc],pref[maxc], opt[maxc][maxc], help[maxc][maxc];//,sums[maxc],sums2[maxc],temp[maxc],mins[maxc];
void build(int k)
{
    int prev =k;
    int i,j;
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
        curr[i][j] = 0;
    int start = group*k,stop = min(r-1,group*(k+1));
     for(j=0;j<c-1;j++)
     {
         pref[j+1] = pref[j]+h[start][j];
     }
     for(i=0;i<c;i++)
        for(j=0;j<c;j++)
        curr[i][j] = abs(pref[i]-pref[j]);
   //cout<<"INITIAL"<<prev<<" ={"<<endl;
     /*for(i=0;i<c;i++){
        for(j=0;j<c;j++)
        cout<<curr[i][j]<<" ";
     cout<<endl;}
     cout<<" }"<<endl;*/
    /* for(int t = start; t<stop;t++)
     {
         cout<<v[t][0]<<endl;
     }
     cout<<"&&"<<endl;*/
     for(int t=start+1; t<=stop;t++)
     {
          for(j=0;j<c-1;j++)
          {
            pref[j+1] = pref[j]+h[t][j];
          }
          for(i=0;i<c;i++)
            for(j=0;j<c;j++)
          {
              help[i][j] = inf;
              opt[i][j]=  -1;
          }
          for(i=0;i<c;i++)
          {
              for(j=0;j<c;j++)
              {
                  int w = curr[i][j] + v[t-1][j] + pref[j];
                  if(help[i][0]>w)
                  {
                      help[i][0] = w;
                      opt[i][0] = j;
                  }
              }
               for(j=0;j<c;j++)
              {
                  int w = curr[i][j] + v[t-1][j] + pref[c-1]-pref[j];
                  if(help[i][c-1]>w)
                  {
                      help[i][c-1] = w;
                      opt[i][c-1] = j;
                  }
              }
          }

          for(i=1;i<c-1;i++)opt[c][i] = c-1;
          for(int diff = -c; diff<=c; diff++)
          {//cout<<diff<<endl;

              for(i=0;i<c;i++)
              {

                  int k = i+diff;
                  if(k<=0||k>=c-1)continue;
                  if(opt[i][k]!=-1)continue;//cout<<" "<<i<<" "<<k<<":: "<<opt[i][k-1]<<" "<<opt[i+1][k]<<endl;
                  for(int p = opt[i][k-1]; p <= opt[i+1][k]; p++)
                  {
                      if(help[i][k]>curr[i][p]+v[t-1][p]+abs(pref[p]-pref[k]))
                         {
                             help[i][k]=curr[i][p]+v[t-1][p]+abs(pref[p]-pref[k]);
                                opt[i][k] = p;
                         }
                  }
              }
          }
          for(i=0;i<c;i++)
            for(j=0;j<c;j++)
            curr[i][j]= help[i][j];
/*cout<<prev<<" <-> "<<t<<" ={"<<endl;
     for(i=0;i<c;i++){
        for(j=0;j<c;j++)
        cout<<curr[i][j]<<" ";
     cout<<endl;}*/
     }
     /*cout<<" }"<<endl;*/
    /* cout<<prev<<" ={"<<endl;
     for(i=0;i<c;i++){
        for(j=0;j<c;j++)
        cout<<curr[i][j]<<" ";
     cout<<endl;}
     cout<<" }"<<endl;*/

}
void update(int v, int l, int r, int d)
{ int i,j;
//cout<<v<<" : "<<l<<" "<<r<<" "<<d<<endl;
    if(l==r)
    {
       for(i=0;i<c;i++)
        for(j=0;j<c;j++)
        segm[v][i][j]= curr[i][j];
        return ;
    }
    int mid = (l+r)/2;
    if(d<=mid)
    update(2*v,l,mid,d);
    else
    update(2*v+1,mid+1,r,d);
    memset(opt,-1,sizeof(opt));
    for(i=0;i<c;i++)
    {
        for(j=0;j<c;j++)
        {
            int cur = segm[2*v][i][j] + segm[2*v+1][j][0];
            if(opt[i][0]==-1||help[i][0]>cur)
            {
                help[i][0] = cur;
                opt[i][0] = j;
            }
            cur = segm[2*v][i][j] + segm[2*v+1][j][c-1];
            if(opt[i][c-1]==-1||help[i][c-1]>cur)
            {
                help[i][c-1] = cur;
                opt[i][c-1] = j;
            }
        }
    }
    for(int diff=-c; diff<=c; diff++)
    {
        for(i=0;i<c;i++)
        {
            int k = i+diff;
            if(k<=0||k>=c-1)continue;
            if(opt[i][k]!=-1)continue;
            for(j=opt[i][k-1];j<=opt[i+1][k];j++)
            {
                int cur = segm[2*v][i][j] + segm[2*v+1][j][k];
                if(help[i][k]>cur||opt[i][k]==-1)
                {
                    help[i][k] = cur;
                    opt[i][k] = j;
                }
            }
        }
    }
    for(i=0;i<c;i++)
        for(j=0;j<c;j++)
        segm[v][i][j] = help[i][j];
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    int i,j;
    r = R;
    c = C;
    for(i=0;i<R;i++)
        for(j=0;j<C-1;j++)
            h[i][j]=H[i][j];
    for(i=0;i<R-1;i++)
        for(j=0;j<C;j++)
            v[i][j]=V[i][j];

    for(i=0;i*group<r;i++)
    {
        //cout<<i<<endl;
        build(i);
       // cout<<i<<endl;
        update(1,0,(r-1)/group,i);
        //cout<<i<<endl;
    }
}

void changeH(int P, int Q, int W) {
    /* ... */
    h[P][Q] = W;
    build(P/group);
    update(1,0,(r-1)/group,P/group);
}

void changeV(int P, int Q, int W) {
    /* ... */
    v[P][Q] = W;
    build(P/group);
    update(1,0,(r-1)/group,P/group);
}

int escape(int V1, int V2) {
    return segm[1][V1][V2];
}

Compilation message (stderr)

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: In function 'void build(int)':
wombats.cpp:14:9: warning: unused variable 'prev' [-Wunused-variable]
   14 |     int prev =k;
      |         ^~~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:115:8: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  115 |        for(i=0;i<c;i++)
      |        ^~~
wombats.cpp:118:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  118 |         return ;
      |         ^~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24