oj.uz

답안 #64530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64530 2018-08-04T19:57:21 Z TadijaSebez 웜뱃 (IOI13_wombats) C++11
76 / 100
 6739 ms 263168 KB 
#include "wombats.h"
#include <stdio.h>
const int N=5050;
const int M=2048;
const int H=205;
const int inf=1e9+7;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
int n,m,dp[M][H][H],ls[M],rs[M],x[N][M],y[N][M],tsz,root,opt[H];
void Take(int c)
{
	int i,j,k,l,r;
	for(i=0;i<m;i++) opt[i]=0;
	for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]=inf;
	for(i=m-1;i>-m;i--)
	{
		for(j=min(m-1,m-i-1);j+min(i,0)>=0;j--)
		{
			if(j==max(-i,0)) l=0;
			else l=opt[j-1];
			if(j==min(m-1,m-i-1)) r=m-1;
			else r=opt[j];
			for(k=l;k<=r;k++)
			{
				if(dp[c][j][j+i]>dp[ls[c]][j][k]+dp[rs[c]][k][j+i])
				{
					dp[c][j][j+i]=dp[ls[c]][j][k]+dp[rs[c]][k][j+i];
					opt[j]=k;
				}
			}
		}
	}
}
void Make(int c, int ss, int se)
{
	int i,j,k;
	for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]=inf;
	for(i=0;i<m;i++) dp[c][i][i]=0;
	for(k=ss;k<=se;k++)
	{
		for(i=0;i<m;i++)
		{
			for(j=1;j<m;j++) dp[c][i][j]=min(dp[c][i][j],dp[c][i][j-1]+x[k][j-1]);
			for(j=m-2;~j;j--) dp[c][i][j]=min(dp[c][i][j],dp[c][i][j+1]+x[k][j]);
		}
		for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]+=y[k][j];
	}
}
void Build(int &c, int ss, int se)
{
	c=++tsz;
	if(se-ss+1<=10)
	{
		Make(c,ss,se);
		return;
	}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
	Take(c);
}
void Upd(int c, int ss, int se, int qi)
{
	if(se-ss+1<=10)
	{
		Make(c,ss,se);
		return;
	}
	int mid=ss+se>>1;
	if(qi<=mid) Upd(ls[c],ss,mid,qi);
	else Upd(rs[c],mid+1,se,qi);
	Take(c);
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
	n=R;m=C;
	int i,j;
	for(i=0;i<n;i++) for(j=0;j<m-1;j++) x[i][j]=H[i][j];
	for(i=0;i<n-1;i++) for(j=0;j<m;j++) y[i][j]=V[i][j];
	Build(root,0,n-1);
}
void changeH(int p, int q, int w){ x[p][q]=w;Upd(root,0,n-1,p);}
void changeV(int p, int q, int w){ y[p][q]=w;Upd(root,0,n-1,p);}
int escape(int a, int b){ return dp[root][a][b];}
//------------------//
/*
int _V[5000][200],_H[5000][200];
int main()
{
	int R,C,i,j,Q,p,q,w,a,b,t;
	scanf("%i %i",&R,&C);
	for(i=0;i<R;i++) for(j=0;j<C-1;j++) scanf("%i",&_H[i][j]);
	for(i=0;i<R-1;i++) for(j=0;j<C;j++) scanf("%i",&_V[i][j]);
	init(R,C,_H,_V);
	scanf("%i",&Q);
	while(Q--)
	{
		scanf("%i",&t);
		if(t==1)
		{
			scanf("%i %i %i",&p,&q,&w);
			changeH(p,q,w);
		}
		if(t==2)
		{
			scanf("%i %i %i",&p,&q,&w);
			changeV(p,q,w);
		}
		if(t==3)
		{
			scanf("%i %i",&a,&b);
			printf("%i\n",escape(a,b));
		}
	}
	return 0;
}
*/
//------------------//

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;
      ^~~
wombats.cpp: In function 'void Build(int&, int, int)':
wombats.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wombats.cpp: In function 'void Upd(int, int, int, int)':
wombats.cpp:69:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 28792 KB Output is correct
2 Correct 21 ms 28860 KB Output is correct
3 Correct 127 ms 31172 KB Output is correct
4 Correct 27 ms 31172 KB Output is correct
5 Correct 24 ms 31172 KB Output is correct
6 Correct 3 ms 31172 KB Output is correct
7 Correct 2 ms 31172 KB Output is correct
8 Correct 2 ms 31172 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 31172 KB Output is correct
2 Correct 2 ms 31172 KB Output is correct
3 Correct 2 ms 31172 KB Output is correct
4 Correct 2 ms 31172 KB Output is correct
5 Correct 2 ms 31172 KB Output is correct
6 Correct 2 ms 31172 KB Output is correct
7 Correct 2 ms 31172 KB Output is correct
8 Correct 2 ms 31172 KB Output is correct
9 Correct 3 ms 31172 KB Output is correct
10 Correct 2 ms 31172 KB Output is correct
11 Correct 86 ms 31172 KB Output is correct
12 Correct 3 ms 31172 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 31172 KB Output is correct
2 Correct 104 ms 31172 KB Output is correct
3 Correct 153 ms 31172 KB Output is correct
4 Correct 145 ms 31172 KB Output is correct
5 Correct 129 ms 31172 KB Output is correct
6 Correct 2 ms 31172 KB Output is correct
7 Correct 2 ms 31172 KB Output is correct
8 Correct 2 ms 31172 KB Output is correct
9 Correct 610 ms 31172 KB Output is correct
10 Correct 2 ms 31172 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 54400 KB Output is correct
2 Correct 40 ms 54428 KB Output is correct
3 Correct 49 ms 54544 KB Output is correct
4 Correct 77 ms 55212 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 55212 KB Output is correct
2 Correct 117 ms 55212 KB Output is correct
3 Correct 140 ms 55212 KB Output is correct
4 Correct 122 ms 55212 KB Output is correct
5 Correct 123 ms 55212 KB Output is correct
6 Correct 38 ms 55212 KB Output is correct
7 Correct 39 ms 55212 KB Output is correct
8 Correct 40 ms 55212 KB Output is correct
9 Correct 76 ms 55356 KB Output is correct
10 Correct 21 ms 55356 KB Output is correct
11 Correct 30 ms 55356 KB Output is correct
12 Correct 91 ms 55356 KB Output is correct
13 Correct 21 ms 55356 KB Output is correct
14 Correct 26 ms 55356 KB Output is correct
15 Correct 2 ms 55356 KB Output is correct
16 Correct 2 ms 55356 KB Output is correct
17 Correct 2 ms 55356 KB Output is correct
18 Correct 4 ms 55356 KB Output is correct
19 Correct 3 ms 55356 KB Output is correct
20 Correct 3 ms 55356 KB Output is correct
21 Correct 3 ms 55356 KB Output is correct
22 Correct 3 ms 55356 KB Output is correct
23 Correct 2 ms 55356 KB Output is correct
24 Correct 2 ms 55356 KB Output is correct
25 Correct 77 ms 55356 KB Output is correct
26 Correct 3 ms 55356 KB Output is correct
27 Correct 488 ms 55356 KB Output is correct
28 Correct 1821 ms 135576 KB Output is correct
29 Correct 1639 ms 135576 KB Output is correct
30 Correct 1693 ms 135576 KB Output is correct
31 Correct 1817 ms 136728 KB Output is correct
32 Correct 3 ms 136728 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 136728 KB Output is correct
2 Correct 102 ms 136728 KB Output is correct
3 Correct 121 ms 136728 KB Output is correct
4 Correct 121 ms 136728 KB Output is correct
5 Correct 118 ms 136728 KB Output is correct
6 Correct 40 ms 136728 KB Output is correct
7 Correct 38 ms 136728 KB Output is correct
8 Correct 43 ms 136728 KB Output is correct
9 Correct 98 ms 136728 KB Output is correct
10 Correct 21 ms 136728 KB Output is correct
11 Correct 21 ms 136728 KB Output is correct
12 Correct 170 ms 136728 KB Output is correct
13 Correct 30 ms 136728 KB Output is correct
14 Correct 21 ms 136728 KB Output is correct
15 Correct 2212 ms 217656 KB Output is correct
16 Correct 6739 ms 219244 KB Output is correct
17 Correct 2 ms 219244 KB Output is correct
18 Correct 2 ms 219244 KB Output is correct
19 Correct 2 ms 219244 KB Output is correct
20 Correct 3 ms 219244 KB Output is correct
21 Correct 4 ms 219244 KB Output is correct
22 Correct 4 ms 219244 KB Output is correct
23 Correct 4 ms 219244 KB Output is correct
24 Correct 11 ms 219244 KB Output is correct
25 Correct 3 ms 219244 KB Output is correct
26 Correct 3 ms 219244 KB Output is correct
27 Correct 100 ms 219244 KB Output is correct
28 Correct 4 ms 219244 KB Output is correct
29 Correct 572 ms 219244 KB Output is correct
30 Correct 1736 ms 219244 KB Output is correct
31 Correct 6485 ms 231428 KB Output is correct
32 Correct 6534 ms 239176 KB Output is correct
33 Correct 1723 ms 239176 KB Output is correct
34 Correct 5822 ms 241004 KB Output is correct
35 Correct 1599 ms 241004 KB Output is correct
36 Correct 6286 ms 251500 KB Output is correct
37 Correct 1852 ms 251500 KB Output is correct
38 Runtime error 6427 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
39 Halted 0 ms 0 KB -