Submission #428521

#	Time	Username	Problem	Language	Result	Execution time	Memory
428521		rumen_m	Wombats (IOI13_wombats)	C++17	0 / 100	58 ms	33156 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxc = 205;
const int maxr = 5005;
const int group = 10;
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 i,j;
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
        curr[i][j] = 0;
    int start = 10*k,stop = min(r-1,10*(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]);
     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[i-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[i-1][j] + pref[c-1]-pref[j];
                  if(help[i][c-1]>w)
                  {
                      help[i][c-1] = w;
                      opt[i][c-1] = j;
                  }
              }
          }
          for(int diff = -c; diff<=c; diff++)
          {
              opt[c][k] = c-1;
              for(i=0;i<c;i++)
              {
                  int k = i+diff;
                  if(k<=0&&k>=c-1)continue;
                  if(opt[i][k]!=0)continue;
                  for(int p = opt[i][k-1]; p <= opt[i+1][k]; i++)
                  {
                      if(help[i][k]>curr[i][p]+v[i-1][p]+abs(pref[p]-pref[k]))
                         {
                             help[i][k]=curr[i][p]+v[i-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];

     }

}
void update(int v, int l, int r, int d)
{ int i,j;
    if(l==r)
    {
       for(i=0;i<c;i++)
        for(j=0;j<c;j++)
        segm[v][i][j]= curr[i][j];
    }
    int mid = (l+r)/2;
    update(2*v,l,mid,d);
    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])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++)
    {
        build(i);
        update(1,0,(r-1)/group,i);
    }
}

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;
      |      ^~~

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