oj.uz

Submission #225254

# Submission time Handle Problem Language Result Execution time Memory
225254 2020-04-20T01:33:12 Z urd05 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 38652 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;

struct Node {
    int arr[200][200];
};

int r,c;
const int bs=70;

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 922 ms 9080 KB Output is correct
2 Correct 934 ms 8960 KB Output is correct
3 Correct 988 ms 11896 KB Output is correct
4 Correct 907 ms 9080 KB Output is correct
5 Correct 905 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 5 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 91 ms 3040 KB Output is correct
12 Correct 5 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 1536 KB Output is correct
2 Correct 637 ms 1572 KB Output is correct
3 Correct 574 ms 1600 KB Output is correct
4 Correct 528 ms 1536 KB Output is correct
5 Correct 639 ms 1656 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
9 Correct 3190 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 970 ms 16928 KB Output is correct
2 Correct 922 ms 17148 KB Output is correct
3 Correct 965 ms 17016 KB Output is correct
4 Correct 1006 ms 18424 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 1536 KB Output is correct
2 Correct 638 ms 1656 KB Output is correct
3 Correct 582 ms 1584 KB Output is correct
4 Correct 543 ms 1656 KB Output is correct
5 Correct 646 ms 1656 KB Output is correct
6 Correct 949 ms 17272 KB Output is correct
7 Correct 950 ms 17144 KB Output is correct
8 Correct 914 ms 17144 KB Output is correct
9 Correct 1010 ms 18424 KB Output is correct
10 Correct 940 ms 9080 KB Output is correct
11 Correct 964 ms 9024 KB Output is correct
12 Correct 1022 ms 11896 KB Output is correct
13 Correct 954 ms 9080 KB Output is correct
14 Correct 1040 ms 9080 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 5 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 5 ms 640 KB Output is correct
24 Correct 5 ms 640 KB Output is correct
25 Correct 89 ms 2936 KB Output is correct
26 Correct 6 ms 640 KB Output is correct
27 Correct 3232 ms 1664 KB Output is correct
28 Correct 6964 ms 27128 KB Output is correct
29 Correct 6668 ms 23144 KB Output is correct
30 Correct 6680 ms 22996 KB Output is correct
31 Correct 6943 ms 28680 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 284 ms 1584 KB Output is correct
2 Correct 641 ms 1656 KB Output is correct
3 Correct 577 ms 1620 KB Output is correct
4 Correct 535 ms 1724 KB Output is correct
5 Correct 641 ms 1656 KB Output is correct
6 Correct 958 ms 17016 KB Output is correct
7 Correct 966 ms 17016 KB Output is correct
8 Correct 934 ms 17016 KB Output is correct
9 Correct 996 ms 18552 KB Output is correct
10 Correct 907 ms 9172 KB Output is correct
11 Correct 935 ms 9080 KB Output is correct
12 Correct 1064 ms 11768 KB Output is correct
13 Correct 896 ms 9080 KB Output is correct
14 Correct 929 ms 9080 KB Output is correct
15 Correct 2243 ms 38008 KB Output is correct
16 Execution timed out 20086 ms 38652 KB Time limit exceeded
17 Halted 0 ms 0 KB -