oj.uz

Submission #227145

# Submission time Handle Problem Language Result Execution time Memory
227145 2020-04-26T09:12:33 Z urd05 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 29688 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
 
struct Node {
    int arr[200][200];
};
 
int r,c;
const int bs=70;
int opt[200][200];
 
inline Node merge(Node l,Node r) {
    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];
int dist[200];
 
void update(int node,int nodel,int noder) {
    for(int st=0;st<c;st++) {
        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 913 ms 8996 KB Output is correct
2 Correct 978 ms 8996 KB Output is correct
3 Correct 1054 ms 10528 KB Output is correct
4 Correct 956 ms 9004 KB Output is correct
5 Correct 1045 ms 8996 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 7 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 616 KB Output is correct
8 Correct 6 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 92 ms 1632 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 294 ms 1408 KB Output is correct
2 Correct 689 ms 1500 KB Output is correct
3 Correct 622 ms 1520 KB Output is correct
4 Correct 560 ms 1516 KB Output is correct
5 Correct 649 ms 1508 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 3296 ms 1536 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 931 ms 16888 KB Output is correct
2 Correct 966 ms 16968 KB Output is correct
3 Correct 1002 ms 16864 KB Output is correct
4 Correct 939 ms 17912 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 1408 KB Output is correct
2 Correct 638 ms 1408 KB Output is correct
3 Correct 585 ms 1408 KB Output is correct
4 Correct 535 ms 1536 KB Output is correct
5 Correct 653 ms 1536 KB Output is correct
6 Correct 944 ms 16972 KB Output is correct
7 Correct 890 ms 16768 KB Output is correct
8 Correct 890 ms 17016 KB Output is correct
9 Correct 976 ms 17788 KB Output is correct
10 Correct 912 ms 9000 KB Output is correct
11 Correct 954 ms 8960 KB Output is correct
12 Correct 993 ms 10616 KB Output is correct
13 Correct 963 ms 9080 KB Output is correct
14 Correct 938 ms 8952 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 88 ms 1656 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 3204 ms 1528 KB Output is correct
28 Correct 6788 ms 23248 KB Output is correct
29 Correct 6521 ms 19320 KB Output is correct
30 Correct 6674 ms 19504 KB Output is correct
31 Correct 6890 ms 24312 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 279 ms 1408 KB Output is correct
2 Correct 644 ms 1528 KB Output is correct
3 Correct 578 ms 1528 KB Output is correct
4 Correct 539 ms 1528 KB Output is correct
5 Correct 642 ms 1528 KB Output is correct
6 Correct 931 ms 16888 KB Output is correct
7 Correct 968 ms 17016 KB Output is correct
8 Correct 943 ms 16992 KB Output is correct
9 Correct 1036 ms 17656 KB Output is correct
10 Correct 939 ms 9080 KB Output is correct
11 Correct 918 ms 8960 KB Output is correct
12 Correct 1004 ms 10616 KB Output is correct
13 Correct 901 ms 9080 KB Output is correct
14 Correct 922 ms 9080 KB Output is correct
15 Correct 2251 ms 28200 KB Output is correct
16 Execution timed out 20027 ms 29688 KB Time limit exceeded
17 Halted 0 ms 0 KB -