oj.uz

Submission #358285

# Submission time Handle Problem Language Result Execution time Memory
358285 2021-01-25T09:41:21 Z Kerim Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 88896 KB 
#include "wombats.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int R=5005,C=202;
int h[R][C],v[R][C],n,m;
struct node{
	vector<vector<int> >dp;	
	void init(){
		dp.resize(m);
		for(int i=0;i<m;i++)
			dp[i].resize(m);
	}
	void fill(){
		init();
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				dp[i][j]=INF;
	}
	void print(){
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++)
				printf("%d ",dp[i][j]);
			puts("");
		}
	}
}seg[R<<2];
int opt[C][C];
node merge(node x,node y,int mid){
	node z;z.fill();
	for(int len=0;len<m;len++){
		for(int i=0,k;i+len<m;i++){
			k=i+len;
			if(i==k){
				for(int j=0;j<m;j++)
					if(umin(z.dp[i][k],x.dp[i][j]+v[mid][j]+y.dp[j][k]))
						opt[i][k]=j;
			}
			else{
				for(int j=opt[i][k-1];j<=opt[i+1][k];j++)
					if(umin(z.dp[i][k],x.dp[i][j]+v[mid][j]+y.dp[j][k]))
						opt[i][k]=j;
				
				for(int j=opt[k-1][i];j<=opt[k][i+1];j++)
					if(umin(z.dp[k][i],x.dp[k][j]+v[mid][j]+y.dp[j][i]))
						opt[k][i]=j;
			}	
		}
	}
	for(int i=0;i<m;i++)
		for(int j=0;j<m;j++)
			for(int k=0;k<m;k++)
				umin(z.dp[i][k],x.dp[i][j]+v[mid][j]+y.dp[j][k]);
	return z;
}	
const int L=15;
int odp[L][C];
node noob(int x){
	node z;z.init();
	for(int i=0;i<m;i++){
		int cur=0;
		for(int j=i;j<m;j++){
			z.dp[i][j]=cur;
			if(j<m-1)
				cur+=h[x][j];
		}cur=0;
		for(int j=i-1;j>=0;j--){
			cur+=h[x][j];
			z.dp[i][j]=cur;
		}
	}
	return z;
}	
void naive(int nd,int x,int y){
	seg[nd]=noob(x);
	for(int i=x;i<y;i++)
		seg[nd]=merge(seg[nd],noob(i+1),i);
}
void build(int nd,int x,int y){
	seg[nd].init();
	if(y-x<L){
		naive(nd,x,y);
		return;			
	}
	int mid=(x+y)>>1;
	build(nd<<1,x,mid);
	build(nd<<1|1,mid+1,y);
	seg[nd]=merge(seg[nd<<1],seg[nd<<1|1],mid);
}
void upd(int p,int nd,int x,int y){
	if(y-x<L){
		naive(nd,x,y);	
		return;
	}
	int mid=(x+y)>>1;
	if(p<=mid)upd(p,nd<<1,x,mid);
	else upd(p,nd<<1|1,mid+1,y);
	seg[nd]=merge(seg[nd<<1],seg[nd<<1|1],mid);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n=R;m=C;
	for(int i=0;i<n;i++)
		for(int j=0;j<m-1;j++)
			h[i][j]=H[i][j];
	for(int i=0;i<n-1;i++)
		for(int j=0;j<m;j++)
			v[i][j]=V[i][j];
	build(1,0,n-1);
}
void changeH(int P, int Q, int W) {
	h[P][Q]=W;upd(P,1,0,n-1);
}
void changeV(int P, int Q, int W) {
	v[P][Q]=W;upd(P,1,0,n-1);
}
int escape(int V1, int V2) {
    return seg[1].dp[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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8684 KB Output is correct
2 Correct 10 ms 8684 KB Output is correct
3 Correct 87 ms 10348 KB Output is correct
4 Correct 10 ms 8684 KB Output is correct
5 Correct 8 ms 8684 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 86 ms 1956 KB Output is correct
12 Correct 2 ms 876 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2057 ms 2156 KB Output is correct
2 Correct 2040 ms 2156 KB Output is correct
3 Correct 2159 ms 2064 KB Output is correct
4 Correct 2247 ms 2004 KB Output is correct
5 Correct 2216 ms 2124 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 9806 ms 2056 KB Output is correct
10 Correct 1 ms 876 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16620 KB Output is correct
2 Correct 17 ms 16620 KB Output is correct
3 Correct 19 ms 16620 KB Output is correct
4 Correct 65 ms 17516 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2211 ms 2052 KB Output is correct
2 Correct 2017 ms 2040 KB Output is correct
3 Correct 2789 ms 2056 KB Output is correct
4 Correct 2229 ms 2056 KB Output is correct
5 Correct 2216 ms 2044 KB Output is correct
6 Correct 23 ms 16768 KB Output is correct
7 Correct 17 ms 16620 KB Output is correct
8 Correct 19 ms 16620 KB Output is correct
9 Correct 57 ms 17516 KB Output is correct
10 Correct 8 ms 8684 KB Output is correct
11 Correct 9 ms 8684 KB Output is correct
12 Correct 87 ms 10380 KB Output is correct
13 Correct 9 ms 8684 KB Output is correct
14 Correct 11 ms 8684 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 2 ms 876 KB Output is correct
19 Correct 2 ms 876 KB Output is correct
20 Correct 2 ms 876 KB Output is correct
21 Correct 1 ms 876 KB Output is correct
22 Correct 1 ms 876 KB Output is correct
23 Correct 2 ms 876 KB Output is correct
24 Correct 2 ms 876 KB Output is correct
25 Correct 91 ms 1900 KB Output is correct
26 Correct 1 ms 876 KB Output is correct
27 Correct 10246 ms 2056 KB Output is correct
28 Correct 19599 ms 61260 KB Output is correct
29 Correct 17255 ms 58420 KB Output is correct
30 Correct 17271 ms 58516 KB Output is correct
31 Correct 18903 ms 62364 KB Output is correct
32 Correct 1 ms 876 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2141 ms 2048 KB Output is correct
2 Correct 1968 ms 2028 KB Output is correct
3 Correct 2077 ms 2028 KB Output is correct
4 Correct 2076 ms 2028 KB Output is correct
5 Correct 2037 ms 2044 KB Output is correct
6 Correct 17 ms 16748 KB Output is correct
7 Correct 16 ms 16620 KB Output is correct
8 Correct 17 ms 16748 KB Output is correct
9 Correct 57 ms 17516 KB Output is correct
10 Correct 8 ms 8684 KB Output is correct
11 Correct 9 ms 8684 KB Output is correct
12 Correct 87 ms 10348 KB Output is correct
13 Correct 9 ms 8684 KB Output is correct
14 Correct 9 ms 8684 KB Output is correct
15 Execution timed out 20027 ms 88896 KB Time limit exceeded
16 Halted 0 ms 0 KB -