oj.uz

Submission #358253

# Submission time Handle Problem Language Result Execution time Memory
358253 2021-01-25T09:01:08 Z Kerim Wombats (IOI13_wombats) C++17
55 / 100
 7166 ms 262148 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[MAXN<<2];
node merge(node x,node y,int mid){
	node z;z.fill();
	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;
}	
void naive(int nd,int x){
	for(int i=0;i<m;i++){
		int cur=0;
		for(int j=i;j<m;j++){
			seg[nd].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];
			seg[nd].dp[i][j]=cur;
		}
	}		
}
void build(int nd,int x,int y){
	seg[nd].init();
	if(x==y){
		naive(nd,x);
		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(x==y){
		naive(nd,x);	
		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 18 ms 18156 KB Output is correct
2 Correct 16 ms 18156 KB Output is correct
3 Correct 102 ms 19948 KB Output is correct
4 Correct 16 ms 18156 KB Output is correct
5 Correct 16 ms 18156 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 ms 9708 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 8 ms 9836 KB Output is correct
6 Correct 8 ms 9836 KB Output is correct
7 Correct 8 ms 9836 KB Output is correct
8 Correct 8 ms 9836 KB Output is correct
9 Correct 8 ms 9836 KB Output is correct
10 Correct 8 ms 9836 KB Output is correct
11 Correct 89 ms 11068 KB Output is correct
12 Correct 9 ms 9836 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 18796 KB Output is correct
2 Correct 915 ms 18708 KB Output is correct
3 Correct 1026 ms 18924 KB Output is correct
4 Correct 1037 ms 18996 KB Output is correct
5 Correct 985 ms 18796 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 ms 9708 KB Output is correct
9 Correct 4343 ms 18892 KB Output is correct
10 Correct 7 ms 9708 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26732 KB Output is correct
2 Correct 24 ms 26732 KB Output is correct
3 Correct 23 ms 26732 KB Output is correct
4 Correct 73 ms 27756 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 18796 KB Output is correct
2 Correct 943 ms 18684 KB Output is correct
3 Correct 1037 ms 18972 KB Output is correct
4 Correct 1049 ms 19052 KB Output is correct
5 Correct 992 ms 18668 KB Output is correct
6 Correct 23 ms 26732 KB Output is correct
7 Correct 24 ms 26732 KB Output is correct
8 Correct 24 ms 26732 KB Output is correct
9 Correct 66 ms 27756 KB Output is correct
10 Correct 16 ms 18284 KB Output is correct
11 Correct 16 ms 18284 KB Output is correct
12 Correct 98 ms 20972 KB Output is correct
13 Correct 17 ms 18284 KB Output is correct
14 Correct 16 ms 18284 KB Output is correct
15 Correct 7 ms 9836 KB Output is correct
16 Correct 7 ms 9708 KB Output is correct
17 Correct 8 ms 9708 KB Output is correct
18 Correct 8 ms 9964 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 8 ms 9964 KB Output is correct
21 Correct 8 ms 9964 KB Output is correct
22 Correct 9 ms 9836 KB Output is correct
23 Correct 8 ms 9836 KB Output is correct
24 Correct 8 ms 9836 KB Output is correct
25 Correct 90 ms 12268 KB Output is correct
26 Correct 9 ms 9964 KB Output is correct
27 Correct 4327 ms 18924 KB Output is correct
28 Runtime error 3698 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 18856 KB Output is correct
2 Correct 982 ms 18668 KB Output is correct
3 Correct 1118 ms 18768 KB Output is correct
4 Correct 1041 ms 18936 KB Output is correct
5 Correct 989 ms 18796 KB Output is correct
6 Correct 23 ms 26732 KB Output is correct
7 Correct 24 ms 26732 KB Output is correct
8 Correct 24 ms 26732 KB Output is correct
9 Correct 67 ms 27756 KB Output is correct
10 Correct 16 ms 18188 KB Output is correct
11 Correct 16 ms 18284 KB Output is correct
12 Correct 99 ms 20972 KB Output is correct
13 Correct 17 ms 18284 KB Output is correct
14 Correct 16 ms 18284 KB Output is correct
15 Runtime error 7166 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -