#include "wombats.h"
#include<algorithm>
using namespace std;
int maxi,r,c,h[5010][210],v[5010][210],tree[1010][210][210],d[11][210][210],arr[210],top,D[11][210][210],imsi[210],t;
void Merge(int x)
{
int i,j,k,l,w=0; x/=2;
while(x){
if(x*2+1>maxi){
for(i=1;i<=c;i++){
for(j=1;j<=c;j++){
tree[x][i][j]=tree[x*2][i][j];
}
}
x/=2; continue;
}
arr[1]=1, arr[2]=c;
for(j=c;j>=1;j--){
for(k=1;k<=c-j+1;k++){
tree[x][k][k+j-1]=2147483647;
for(l=arr[k];l<=arr[k+1];l++){
if(tree[x][k][k+j-1]>tree[x*2][k][l]+tree[x*2+1][l][k+j-1]) tree[x][k][k+j-1]=tree[x*2][k][l]+tree[x*2+1][l][k+j-1], imsi[k]=l;
}
}
for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
arr[1]=1; arr[c-j+3]=c;
}
arr[1]=1, arr[2]=c;
for(j=c;j>=1;j--){
for(k=1;k<=c-j+1;k++){
tree[x][k+j-1][k]=2147483647;
for(l=arr[k];l<=arr[k+1];l++){
if(tree[x][k+j-1][k]>tree[x*2][k+j-1][l]+tree[x*2+1][l][k]) tree[x][k+j-1][k]=tree[x*2][k+j-1][l]+tree[x*2+1][l][k], imsi[k]=l;
}
}
for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
arr[1]=1; arr[c-j+3]=c;
}
x/=2;
}
}
void update(int x)
{
int p,i,j,k,l,w=0,s1,s2;
for(i=(x-1)*10+1;i<=min(r-1,(x-1)*10+10);i++){
w++; arr[1]=1, arr[2]=c;
for(j=c;j>=1;j--){
for(k=1;k<=c-j+1;k++){
d[w][k][k+j-1]=2147483647;
for(l=arr[k];l<=arr[k+1];l++){
p=v[i][l];
if(l>=k) s1=1; else s1=-1;
if(l<=k+j-1) s2=1; else s2=-1;
p=v[i][l]+s2*(h[i+1][k+j-2]-h[i+1][l-1])+s1*(h[i][l-1]-h[i][k-1]);
if(d[w][k][k+j-1]>p) d[w][k][k+j-1]=p, imsi[k]=l;
}
}
for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
arr[1]=1; arr[c-j+3]=c;
}
arr[1]=1, arr[2]=c;
for(j=c;j>=1;j--){
for(k=1;k<=c-j+1;k++){
d[w][k+j-1][k]=2147483647;
for(l=arr[k];l<=arr[k+1];l++){
if(l>=k+j-1) s1=-1; else s1=1;
if(l>=k) s2=1; else s2=-1;
p=v[i][l]+s1*(h[i][k+j-2]-h[i][l-1])+s2*(h[i+1][l-1]-h[i+1][k-1]);
if(d[w][k+j-1][k]>p) d[w][k+j-1][k]=p, imsi[k]=l;
}
}
for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
arr[1]=1; arr[c-j+3]=c;
}
}
for(i=1;i<=c;i++){
for(j=1;j<=c;j++){
D[1][i][j]=d[1][i][j];
}
}
for(i=2;i<=w;i++){
arr[1]=1, arr[2]=c;
for(j=c;j>=1;j--){
for(k=1;k<=c-j+1;k++){
D[i][k][k+j-1]=2147483647;
for(l=arr[k];l<=arr[k+1];l++){
p=D[i-1][k][l]+d[i][l][k+j-1];
if(D[i][k][k+j-1]>p) D[i][k][k+j-1]=p, imsi[k]=l;
}
}
for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
arr[1]=1; arr[c-j+3]=c;
}
arr[1]=1, arr[2]=c;
for(j=c;j>=1;j--){
for(k=1;k<=c-j+1;k++){
D[i][k+j-1][k]=2147483647;
for(l=arr[k];l<=arr[k+1];l++){
p=D[i-1][k+j-1][l]+d[i][l][k];
if(D[i][k+j-1][k]>p) D[i][k+j-1][k]=p, imsi[k]=l;
}
}
for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
arr[1]=1; arr[c-j+3]=c;
}
}
maxi=max(maxi,x+t-1);
for(i=1;i<=c;i++){
for(j=1;j<=c;j++){
tree[x+t-1][i][j]=D[w][i][j];
}
}
Merge(x+t-1);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r=R; c=C;
int i,j;
for(i=1;i<=r;i++){
for(j=1;j<=c-1;j++){
h[i][j]=h[i][j-1]+H[i-1][j-1];
}
}
for(i=1;i<=r-1;i++){
for(j=1;j<=c;j++){
v[i][j]=V[i-1][j-1];
}
}
for(t=1;t<(r-2)/10+1;t*=2);
for(i=1;i<=(r-1)/10+1;i++) update(i);
}
void changeH(int P, int Q, int W) {
int i,j,s; P++; Q++;
s=W-(h[P][Q]-h[P][Q-1]);
for(i=Q;i<=c-1;i++) h[P][i]+=s;
if(P==r) P--;
update((P-1)/10+1);
}
void changeV(int P, int Q, int W) {
v[P+1][Q+1]=W;
update((P-1)/10+1);
}
int escape(int V1, int V2) {
return tree[1][V1+1][V2+1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
194900 KB |
Output is correct - 505 tokens |
2 |
Incorrect |
0 ms |
194900 KB |
Output isn't correct - 12th words differ - expected: '2501154', found: '2501148' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
194900 KB |
Output is correct - 6 tokens |
2 |
Correct |
0 ms |
194900 KB |
Output is correct - 6 tokens |
3 |
Correct |
0 ms |
194900 KB |
Output is correct - 6 tokens |
4 |
Correct |
0 ms |
194900 KB |
Output is correct - 405 tokens |
5 |
Correct |
0 ms |
194900 KB |
Output is correct - 405 tokens |
6 |
Correct |
0 ms |
194900 KB |
Output is correct - 405 tokens |
7 |
Correct |
0 ms |
194900 KB |
Output is correct - 405 tokens |
8 |
Correct |
0 ms |
194900 KB |
Output is correct - 366 tokens |
9 |
Correct |
0 ms |
194900 KB |
Output is correct - 405 tokens |
10 |
Correct |
0 ms |
194900 KB |
Output is correct - 366 tokens |
11 |
Correct |
71 ms |
194900 KB |
Output is correct - 200005 tokens |
12 |
Correct |
0 ms |
194900 KB |
Output is correct - 405 tokens |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
439 ms |
194900 KB |
Output isn't correct - 1st words differ - expected: '34137', found: '31737' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
194900 KB |
Output isn't correct - 2nd words differ - expected: '2116711', found: '2116517' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
435 ms |
194900 KB |
Output isn't correct - 1st words differ - expected: '34137', found: '31737' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
435 ms |
194900 KB |
Output isn't correct - 1st words differ - expected: '34137', found: '31737' |
2 |
Halted |
0 ms |
0 KB |
- |