oj.uz

Submission #143255

# Submission time Handle Problem Language Result Execution time Memory
143255 2019-08-13T12:29:36 Z Bodo171 Wombats (IOI13_wombats) C++14
100 / 100
 7825 ms 187624 KB 
#include "wombats.h"
#include <iostream>
#include <fstream>
using namespace std;
const int rmax=5001;
const int cmax=200;
const int buck=10;
int h[rmax][cmax],v[rmax][cmax],dp[rmax][cmax];
int opt[cmax][cmax];
int arb[4*(rmax/buck)][cmax][cmax];
int n,m,i,j,start,sgn,len,k;
void recalc(int nod,int st,int dr)
{
    for(start=0;start<m;start++)
    {
        for(i=0;i<m;i++)
            dp[st][i]=(1<<30);
        dp[st][start]=0;
        for(i=st;i<=dr;i++)
        {
            if(i>st)
               for(j=0;j<m;j++)
                  dp[i][j]=(dp[i-1][j]+v[i-1][j]);
            for(j=1;j<m;j++)
                dp[i][j]=min(dp[i][j],dp[i][j-1]+h[i][j-1]);
            for(j=m-2;j>=0;j--)
                dp[i][j]=min(dp[i][j],dp[i][j+1]+h[i][j]);
        }
        for(j=0;j<m;j++)
            arb[nod][start][j]=dp[dr][j];
    }
}
void mrg(int A[][cmax],int trans[],int st[][cmax],int dr[][cmax])
{
    for(i=0;i<m;i++)
      for(j=0;j<m;j++)
        A[i][j]=(1<<30);
    for(i=0;i<m;i++)
        for(j=0;j<m;j++)
        {
            if(st[i][j]+dr[j][i]+trans[j]<A[i][i])
               A[i][i]=st[i][j]+dr[j][i]+trans[j],opt[0][i]=j;
        }
    int l,r;
    for(sgn=-1;sgn<=1;sgn+=2)
        for(len=1;len<m;len++)
            for(i=0;i<m;i++)
                if(i+len*sgn>=0&&i+len*sgn<m)
        {
            l=opt[len-1][i+sgn];r=opt[len-1][i];
            if(l>r) swap(l,r);
            for(k=l;k<=r;k++)
            {
                if(st[i][k]+dr[k][i+len*sgn]+trans[k]<A[i][i+len*sgn])
                {
                    A[i][i+len*sgn]=st[i][k]+dr[k][i+len*sgn]+trans[k];
                    opt[len][i]=k;
                }
            }
        }
}
void update(int nod,int l,int r,int poz)
{
    if(l==r)
    {
        recalc(nod,poz*buck,min((poz+1)*buck-1,n-1));
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m,poz);
    else update(2*nod+1,m+1,r,poz);
    mrg(arb[nod],v[(m+1)*buck-1],arb[2*nod],arb[2*nod+1]);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n=R;m=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(int p=0;p<=(n-1)/buck;p++)
        update(1,0,(n-1)/buck,p);
}

void changeH(int P, int Q, int W) {
    h[P][Q]=W;
    update(1,0,(n-1)/buck,P/buck);
}
void changeV(int P, int Q, int W) {
    v[P][Q]=W;
    update(1,0,(n-1)/buck,P/buck);
}

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

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16380 KB Output is correct
2 Correct 16 ms 16376 KB Output is correct
3 Correct 89 ms 18040 KB Output is correct
4 Correct 16 ms 16376 KB Output is correct
5 Correct 17 ms 16376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 78 ms 1500 KB Output is correct
12 Correct 3 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2296 KB Output is correct
2 Correct 128 ms 2416 KB Output is correct
3 Correct 145 ms 2428 KB Output is correct
4 Correct 143 ms 2424 KB Output is correct
5 Correct 146 ms 2584 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 585 ms 2500 KB Output is correct
10 Correct 2 ms 380 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24952 KB Output is correct
2 Correct 28 ms 24952 KB Output is correct
3 Correct 26 ms 24824 KB Output is correct
4 Correct 62 ms 25720 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 2424 KB Output is correct
2 Correct 130 ms 2396 KB Output is correct
3 Correct 147 ms 2428 KB Output is correct
4 Correct 142 ms 2424 KB Output is correct
5 Correct 145 ms 2532 KB Output is correct
6 Correct 25 ms 25016 KB Output is correct
7 Correct 25 ms 24952 KB Output is correct
8 Correct 25 ms 24952 KB Output is correct
9 Correct 63 ms 26360 KB Output is correct
10 Correct 16 ms 16376 KB Output is correct
11 Correct 17 ms 16376 KB Output is correct
12 Correct 87 ms 19192 KB Output is correct
13 Correct 16 ms 16376 KB Output is correct
14 Correct 17 ms 16504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 3 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 78 ms 2936 KB Output is correct
26 Correct 3 ms 504 KB Output is correct
27 Correct 580 ms 2512 KB Output is correct
28 Correct 1853 ms 106296 KB Output is correct
29 Correct 1840 ms 87612 KB Output is correct
30 Correct 1869 ms 87548 KB Output is correct
31 Correct 1925 ms 108024 KB Output is correct
32 Correct 2 ms 376 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2424 KB Output is correct
2 Correct 128 ms 2424 KB Output is correct
3 Correct 144 ms 2444 KB Output is correct
4 Correct 142 ms 2420 KB Output is correct
5 Correct 146 ms 2428 KB Output is correct
6 Correct 26 ms 25080 KB Output is correct
7 Correct 25 ms 25080 KB Output is correct
8 Correct 25 ms 24940 KB Output is correct
9 Correct 63 ms 26332 KB Output is correct
10 Correct 16 ms 16376 KB Output is correct
11 Correct 17 ms 16376 KB Output is correct
12 Correct 86 ms 19192 KB Output is correct
13 Correct 17 ms 16376 KB Output is correct
14 Correct 17 ms 16376 KB Output is correct
15 Correct 3843 ms 186500 KB Output is correct
16 Correct 7825 ms 187624 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 528 KB Output is correct
21 Correct 3 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 3 ms 532 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 3 ms 504 KB Output is correct
27 Correct 79 ms 2936 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 582 ms 2424 KB Output is correct
30 Correct 1867 ms 106248 KB Output is correct
31 Correct 7129 ms 185060 KB Output is correct
32 Correct 7071 ms 185112 KB Output is correct
33 Correct 1816 ms 87544 KB Output is correct
34 Correct 7018 ms 153376 KB Output is correct
35 Correct 1870 ms 87464 KB Output is correct
36 Correct 7183 ms 153164 KB Output is correct
37 Correct 1938 ms 107792 KB Output is correct
38 Correct 7095 ms 185744 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 7313 ms 153328 KB Output is correct