oj.uz

Submission #225255

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

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

int r,c;
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[80];
int h[5000][200];
int v[5000][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]) {
    mt19937 rd = mt19937((unsigned)chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> ran(0, 2147483647);
    bs=ran(rd)%10+65;
    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 919 ms 9080 KB Output is correct
2 Correct 978 ms 8960 KB Output is correct
3 Correct 1054 ms 11000 KB Output is correct
4 Correct 970 ms 9080 KB Output is correct
5 Correct 927 ms 9080 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 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 94 ms 2168 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 290 ms 1656 KB Output is correct
2 Correct 638 ms 1536 KB Output is correct
3 Correct 584 ms 1656 KB Output is correct
4 Correct 580 ms 1656 KB Output is correct
5 Correct 641 ms 1536 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 3391 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 1065 ms 17092 KB Output is correct
2 Correct 1024 ms 17020 KB Output is correct
3 Correct 1006 ms 17144 KB Output is correct
4 Correct 1010 ms 18296 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 1632 KB Output is correct
2 Correct 636 ms 1656 KB Output is correct
3 Correct 571 ms 1536 KB Output is correct
4 Correct 523 ms 1592 KB Output is correct
5 Correct 614 ms 1656 KB Output is correct
6 Correct 1025 ms 17080 KB Output is correct
7 Correct 969 ms 16992 KB Output is correct
8 Correct 947 ms 17016 KB Output is correct
9 Correct 1042 ms 18296 KB Output is correct
10 Correct 916 ms 9080 KB Output is correct
11 Correct 879 ms 9080 KB Output is correct
12 Correct 1016 ms 11128 KB Output is correct
13 Correct 898 ms 9020 KB Output is correct
14 Correct 928 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 6 ms 640 KB Output is correct
24 Correct 5 ms 640 KB Output is correct
25 Correct 92 ms 2168 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 3203 ms 1584 KB Output is correct
28 Correct 6976 ms 24000 KB Output is correct
29 Correct 6704 ms 20232 KB Output is correct
30 Correct 6779 ms 20284 KB Output is correct
31 Correct 7038 ms 24488 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 272 ms 1536 KB Output is correct
2 Correct 677 ms 1660 KB Output is correct
3 Correct 591 ms 1656 KB Output is correct
4 Correct 583 ms 1656 KB Output is correct
5 Correct 694 ms 1656 KB Output is correct
6 Correct 1018 ms 17016 KB Output is correct
7 Correct 1034 ms 17120 KB Output is correct
8 Correct 1095 ms 16896 KB Output is correct
9 Correct 1057 ms 18552 KB Output is correct
10 Correct 903 ms 9080 KB Output is correct
11 Correct 925 ms 9080 KB Output is correct
12 Correct 1020 ms 11128 KB Output is correct
13 Correct 878 ms 9012 KB Output is correct
14 Correct 904 ms 8960 KB Output is correct
15 Correct 2293 ms 28704 KB Output is correct
16 Execution timed out 20047 ms 29792 KB Time limit exceeded
17 Halted 0 ms 0 KB -