oj.uz

Submission #227142

# Submission time Handle Problem Language Result Execution time Memory
227142 2020-04-26T09:08:28 Z urd05 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 38716 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
 
struct Node {
    int arr[200][200];
};
 
int r,c;
const int bs=70;
 
inline Node merge(Node l,Node r) {
    int opt[200][200];
    Node ret;
    for(int diff=-c+1;diff<=c-1;diff++) {
        for(int i=max(-diff,0);i<min(c-diff,c);i++) {
            int j=i+diff;
            int st;
            if (j==0) {
                st=0;
            }
            else {
                st=opt[i][j-1];
            }
            int en;
            if (i==c-1) {
                en=c-1;
            }
            else {
                en=opt[i+1][j];
            }
            int mini=2e9;
            for(int k=st;k<=en;k++) {
                if (l.arr[i][k]+r.arr[k][j]<mini) {
                    opt[i][j]=k;
                    mini=l.arr[i][k]+r.arr[k][j];
                }
            }
            ret.arr[i][j]=mini;
        }
    }
    return ret;
}
 
Node tp;
Node arr[72];
int h[5000][199];
int v[4999][200];
 
void update(int node,int nodel,int noder) {
    for(int st=0;st<c;st++) {
        int dist[200];
        dist[st]=0;
        for(int i=st-1;i>=0;i--) {
            dist[i]=dist[i+1]+h[nodel][i];
        }
        for(int i=st+1;i<c;i++) {
            dist[i]=dist[i-1]+h[nodel][i-1];
        }
        for(int i=nodel+1;i<=noder;i++) {
            for(int j=0;j<c;j++) {
                dist[j]=dist[j]+v[i-1][j];
            }
            for(int j=1;j<c;j++) {
                dist[j]=min(dist[j],dist[j-1]+h[i][j-1]);
            }
            for(int j=c-2;j>=0;j--) {
                dist[j]=min(dist[j],dist[j+1]+h[i][j]);
            }
        }
        for(int i=0;i<c;i++) {
            arr[node].arr[st][i]=dist[i];
        }
    }
}
 
void init(int rr,int cc,int hh[][200],int vv[][200]) {
    r=rr;
    c=cc;
    for(int i=0;i<r;i++) {
        for(int j=0;j<c-1;j++) {
            h[i][j]=hh[i][j];
        }
    }
    for(int i=0;i<r-1;i++) {
        for(int j=0;j<c;j++) {
            v[i][j]=vv[i][j];
        }
    }
    for(int i=0;i<=(r-1)/bs;i++) {
        update(i,i*bs,min(i*bs+bs,r-1));
    }
    tp=arr[0];
    for(int i=1;i<=(r-1)/bs;i++) {
        tp=merge(tp,arr[i]);
    }
}
 
void changeH(int p,int q,int w) {
    h[p][q]=w;
    if (p%bs==0&&p!=0) {
        update(p/bs-1,(p/bs-1)*bs,(p/bs-1)*bs+bs);
        update(p/bs,p,min(p+bs,r-1));
    }
    else {
        update(p/bs,(p/bs)*bs,min((p/bs)*bs+bs,r-1));
    }
    tp=arr[0];
    for(int j=1;j<=(r-1)/bs;j++) {
        tp=merge(tp,arr[j]);
    }
}
 
void changeV(int p,int q,int w) {
    v[p][q]=w;
    update(p/bs,(p/bs)*bs,min((p/bs)*bs+bs,r-1));
    tp=arr[0];
    for(int j=1;j<=(r-1)/bs;j++) {
        tp=merge(tp,arr[j]);
    }
}
 
int escape(int v1,int v2) {
    return tp.arr[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 976 ms 9080 KB Output is correct
2 Correct 975 ms 9080 KB Output is correct
3 Correct 1022 ms 11796 KB Output is correct
4 Correct 1008 ms 9080 KB Output is correct
5 Correct 940 ms 9080 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 98 ms 3040 KB Output is correct
12 Correct 6 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 1660 KB Output is correct
2 Correct 661 ms 1656 KB Output is correct
3 Correct 613 ms 1656 KB Output is correct
4 Correct 557 ms 1536 KB Output is correct
5 Correct 664 ms 1656 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 3291 ms 1656 KB Output is correct
10 Correct 5 ms 512 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 17060 KB Output is correct
2 Correct 926 ms 16992 KB Output is correct
3 Correct 913 ms 17016 KB Output is correct
4 Correct 998 ms 18296 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 1536 KB Output is correct
2 Correct 659 ms 1700 KB Output is correct
3 Correct 591 ms 1656 KB Output is correct
4 Correct 547 ms 1536 KB Output is correct
5 Correct 667 ms 1656 KB Output is correct
6 Correct 910 ms 17020 KB Output is correct
7 Correct 972 ms 17016 KB Output is correct
8 Correct 943 ms 17016 KB Output is correct
9 Correct 1006 ms 18424 KB Output is correct
10 Correct 909 ms 8960 KB Output is correct
11 Correct 924 ms 9080 KB Output is correct
12 Correct 1012 ms 11896 KB Output is correct
13 Correct 941 ms 9080 KB Output is correct
14 Correct 955 ms 8960 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 6 ms 640 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 5 ms 640 KB Output is correct
23 Correct 6 ms 640 KB Output is correct
24 Correct 5 ms 640 KB Output is correct
25 Correct 95 ms 3064 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 3303 ms 1656 KB Output is correct
28 Correct 7046 ms 27132 KB Output is correct
29 Correct 6713 ms 23060 KB Output is correct
30 Correct 6744 ms 22736 KB Output is correct
31 Correct 7094 ms 28696 KB Output is correct
32 Correct 5 ms 512 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 1656 KB Output is correct
2 Correct 661 ms 1656 KB Output is correct
3 Correct 603 ms 1536 KB Output is correct
4 Correct 555 ms 1536 KB Output is correct
5 Correct 663 ms 1656 KB Output is correct
6 Correct 942 ms 17144 KB Output is correct
7 Correct 953 ms 17020 KB Output is correct
8 Correct 984 ms 17016 KB Output is correct
9 Correct 1006 ms 18424 KB Output is correct
10 Correct 958 ms 8960 KB Output is correct
11 Correct 955 ms 9080 KB Output is correct
12 Correct 1014 ms 11900 KB Output is correct
13 Correct 994 ms 8960 KB Output is correct
14 Correct 904 ms 9084 KB Output is correct
15 Correct 2308 ms 37776 KB Output is correct
16 Execution timed out 20003 ms 38716 KB Time limit exceeded
17 Halted 0 ms 0 KB -