Submission #164367

#	Time	Username	Problem	Language	Result	Execution time	Memory
164367		costle	Wombats (IOI13_wombats)	C++17	100 / 100	4330 ms	183416 KiB

wombats

#include "wombats.h"
 
#include <stdio.h>
#include <algorithm>
#define INF 1e9
#define ele (1<<9)
#define R 5000
#define C 200
#define BS 10
#define BN R/BS
using namespace std;
int H[R][C-1],V[R][C];
int sgt[ele<<1][C][C],p[C+1];
void update_(int xs,int xe,int w,int l,int r){
	if(l==r){
		for(int i=0;i<C;i++){
            for(int j=0;j<C;j++) sgt[w][i][j]=INF;
		}
		for(int i=0;i<C;i++){
			sgt[w][i][i]=0;
			for(int j=l*BS;j<(l+1)*BS;j++){
				for(int k=1;k<C;k++) sgt[w][i][k]=min(sgt[w][i][k-1]+H[j][k-1],sgt[w][i][k]);
				for(int k=C-1;k;k--) sgt[w][i][k-1]=min(sgt[w][i][k]+H[j][k-1],sgt[w][i][k-1]);
				for(int k=0;k<C;k++) sgt[w][i][k]+=V[j][k];
			}
		}
		return;
	}
	int m=(l+r)>>1;
	if(xs<=m) update_(xs,xe,w<<1,l,m);
	if(m<xe) update_(xs,xe,w<<1|1,m+1,r);
	for(int i=0;i<C;i++) p[i]=0;
	for(int i=0;i<C;i++){
		for(int j=C-1;j>=0;j--){
			int mn=INF,mni=0;
			for(int k=p[j];k<=p[j+1];k++){
                if(mn>=sgt[w<<1][i][k]+sgt[w<<1|1][k][j]) mn=sgt[w<<1][i][k]+sgt[w<<1|1][k][j],mni=k;
			}
			sgt[w][i][j]=mn,p[j]=mni;
		}
	}
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
    for(int i=0;i<R;i++){
        for(int j=0;j<C-1;j++) H[i][j]=INF;
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<c-1;j++) H[i][j]=h[i][j];
    }
    for(int i=0;i<r-1;i++){
        for(int j=0;j<c;j++) V[i][j]=v[i][j];
    }
	p[C]=C-1;
	update_(0,BN-1,1,0,BN-1);
}
 
void changeH(int a, int b, int c) {
	H[a][b]=c;
	update_(a/BS,a/BS,1,0,BN-1);
}
 
void changeV(int a, int b, int c) {
	V[a][b]=c;
	update_(a/BS,a/BS,1,0,BN-1);
}
 
int escape(int a, int b) {
	return sgt[1][a][b];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'void update_(int, int, int, int, int)':
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 void update_(int xs,int xe,int w,int l,int r){
      ^~~~~~~
wombats.cpp:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24