oj.uz

Submission #227179

# Submission time Handle Problem Language Result Execution time Memory
227179 2020-04-26T11:03:24 Z urd05 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 24788 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
 
struct Node {
    int arr[200][200];
};
 
int r,c;
const int bs=121;
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 mini=2e9;
            for(int k=(j==0?0:opt[i][j-1]);k<=(i==c-1?c-1:opt[i+1][j]);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[45];
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 545 ms 8832 KB Output is correct
2 Correct 581 ms 8896 KB Output is correct
3 Correct 664 ms 10504 KB Output is correct
4 Correct 594 ms 8956 KB Output is correct
5 Correct 574 ms 8952 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 88 ms 1656 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 906 ms 1144 KB Output is correct
2 Correct 881 ms 1016 KB Output is correct
3 Correct 923 ms 1016 KB Output is correct
4 Correct 907 ms 896 KB Output is correct
5 Correct 894 ms 1144 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 4446 ms 1016 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 594 ms 16768 KB Output is correct
2 Correct 575 ms 16760 KB Output is correct
3 Correct 594 ms 16640 KB Output is correct
4 Correct 605 ms 17656 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 1016 KB Output is correct
2 Correct 884 ms 1024 KB Output is correct
3 Correct 907 ms 1144 KB Output is correct
4 Correct 901 ms 1016 KB Output is correct
5 Correct 890 ms 1016 KB Output is correct
6 Correct 567 ms 16760 KB Output is correct
7 Correct 555 ms 16760 KB Output is correct
8 Correct 559 ms 16760 KB Output is correct
9 Correct 585 ms 17656 KB Output is correct
10 Correct 548 ms 8832 KB Output is correct
11 Correct 539 ms 8832 KB Output is correct
12 Correct 635 ms 10524 KB Output is correct
13 Correct 573 ms 8956 KB Output is correct
14 Correct 568 ms 8832 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 512 KB Output is correct
27 Correct 4464 ms 1024 KB Output is correct
28 Correct 7809 ms 21048 KB Output is correct
29 Correct 7647 ms 17512 KB Output is correct
30 Correct 7637 ms 17404 KB Output is correct
31 Correct 8038 ms 21556 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 897 ms 1012 KB Output is correct
2 Correct 889 ms 1016 KB Output is correct
3 Correct 903 ms 896 KB Output is correct
4 Correct 923 ms 1016 KB Output is correct
5 Correct 905 ms 1144 KB Output is correct
6 Correct 549 ms 16888 KB Output is correct
7 Correct 554 ms 16888 KB Output is correct
8 Correct 561 ms 16888 KB Output is correct
9 Correct 600 ms 17516 KB Output is correct
10 Correct 548 ms 8832 KB Output is correct
11 Correct 539 ms 8832 KB Output is correct
12 Correct 646 ms 10488 KB Output is correct
13 Correct 562 ms 8896 KB Output is correct
14 Correct 553 ms 8952 KB Output is correct
15 Correct 2279 ms 23596 KB Output is correct
16 Execution timed out 20102 ms 24788 KB Time limit exceeded
17 Halted 0 ms 0 KB -