답안 #13539 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13539	2015-02-23T11:18:24 Z	woqja125	K개의 묶음 (IZhO14_blocks)	C++	100 / 100	556 ms	43932 KB

blocks

#include<stdio.h>
int max(int a, int b){return a>b?a:b;}
int min(int a, int b){return a<b?a:b;}
int dp[101][100001];
int IT[300001];
int IT2[300001];
int b = 1;
int a[100001];
int bb[100001];
int getmin(int f, int r);
int main()
{
    int n, k;
    int i, j;
    scanf("%d%d", &n, &k);
    for(b=1; b<=n; b*=2);
    for(i=1; i<=n; i++) scanf("%d", a+i);
    int stk[100001], top=-1;
	for(i=1; i<=n; i++)
	{
		while(top != -1 && a[stk[top]] < a[i])top--;
		if(top == -1) bb[i] = -1;
		else bb[i] = stk[top];
		stk[++top] = i;
	}
    for(i=1; i<=n; i++) dp[1][i] = max(a[i], dp[1][i-1]);
    for(i=2; i<=k; i++)
    {
    	for(j=1; j<=n; j++) IT[b+j] = dp[i-1][j];
    	for(j=b; j>=1; j--) IT[j] = min(IT[j*2], IT[j*2+1]);
        for(j=i; j<=n; j++)
        {
        	if(bb[j] == -1) dp[i][j] = getmin(i-1, j-1) + a[j];
        	else
        	{
        		if(bb[j] < i)
        		{
        			dp[i][j] = getmin(i-1, j-1) + a[j];
        		}
        		else
        		{
        			dp[i][j] = min(getmin(bb[j], j-1) + a[j], dp[i][bb[j]]);
        		}
        	}
        }
    }
    printf("%d", dp[k][n]);
    return 0;
}

int getmin(int f, int r)
{
    f+=b; r+=b;
    int re = 200000000;
    while(f<r)
    {
        if(f%2 == 1) re = min(re, IT[f++]);
        if(r%2 == 0) re = min(re, IT[r--]);
        f/=2; r/=2;
    }
    if(f==r) re = min(re, IT[f]);
    return re;
}

Subtask #1
14.0 / 14.0

#	결과	메모리	Grader output
1	Correct	43924 KB	Output is correct
2	Correct	43924 KB	Output is correct
3	Correct	43924 KB	Output is correct
4	Correct	43932 KB	Output is correct
5	Correct	43924 KB	Output is correct
6	Correct	43928 KB	Output is correct
7	Correct	43924 KB	Output is correct
8	Correct	43928 KB	Output is correct
9	Correct	43924 KB	Output is correct
10	Correct	43932 KB	Output is correct
11	Correct	43924 KB	Output is correct
12	Correct	43928 KB	Output is correct
13	Correct	43928 KB	Output is correct
14	Correct	43932 KB	Output is correct
15	Correct	43928 KB	Output is correct
16	Correct	43928 KB	Output is correct
17	Correct	43932 KB	Output is correct
18	Correct	43928 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	메모리	Grader output
1	Correct	43924 KB	Output is correct
2	Correct	43928 KB	Output is correct
3	Correct	43928 KB	Output is correct
4	Correct	43932 KB	Output is correct
5	Correct	43924 KB	Output is correct
6	Correct	43924 KB	Output is correct
7	Correct	43924 KB	Output is correct
8	Correct	43924 KB	Output is correct
9	Correct	43924 KB	Output is correct
10	Correct	43932 KB	Output is correct
11	Correct	43928 KB	Output is correct
12	Correct	43928 KB	Output is correct
13	Correct	43924 KB	Output is correct
14	Correct	43924 KB	Output is correct
15	Correct	43924 KB	Output is correct
16	Correct	43928 KB	Output is correct
17	Correct	43924 KB	Output is correct
18	Correct	43928 KB	Output is correct
19	Correct	43928 KB	Output is correct
20	Correct	43928 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	메모리	Grader output
1	Correct	43928 KB	Output is correct
2	Correct	43932 KB	Output is correct
3	Correct	43928 KB	Output is correct
4	Correct	43932 KB	Output is correct
5	Correct	43928 KB	Output is correct
6	Correct	43928 KB	Output is correct
7	Correct	43924 KB	Output is correct
8	Correct	43932 KB	Output is correct
9	Correct	43924 KB	Output is correct
10	Correct	43928 KB	Output is correct
11	Correct	43924 KB	Output is correct
12	Correct	43928 KB	Output is correct
13	Correct	43924 KB	Output is correct
14	Correct	43932 KB	Output is correct
15	Correct	43932 KB	Output is correct
16	Correct	43928 KB	Output is correct
17	Correct	43924 KB	Output is correct
18	Correct	43932 KB	Output is correct
19	Correct	43928 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	43924 KB	Output is correct
2	Correct	0 ms	43928 KB	Output is correct
3	Correct	20 ms	43932 KB	Output is correct
4	Correct	175 ms	43932 KB	Output is correct
5	Correct	556 ms	43932 KB	Output is correct
6	Correct	29 ms	43924 KB	Output is correct
7	Correct	254 ms	43928 KB	Output is correct
8	Correct	0 ms	43924 KB	Output is correct
9	Correct	0 ms	43928 KB	Output is correct
10	Correct	0 ms	43924 KB	Output is correct
11	Correct	0 ms	43924 KB	Output is correct
12	Correct	0 ms	43924 KB	Output is correct
13	Correct	0 ms	43928 KB	Output is correct
14	Correct	22 ms	43928 KB	Output is correct
15	Correct	0 ms	43932 KB	Output is correct
16	Correct	5 ms	43924 KB	Output is correct
17	Correct	0 ms	43924 KB	Output is correct
18	Correct	17 ms	43924 KB	Output is correct
19	Correct	88 ms	43928 KB	Output is correct
20	Correct	249 ms	43928 KB	Output is correct
21	Correct	25 ms	43928 KB	Output is correct
22	Correct	124 ms	43928 KB	Output is correct
23	Correct	0 ms	43924 KB	Output is correct
24	Correct	38 ms	43924 KB	Output is correct
25	Correct	262 ms	43928 KB	Output is correct
26	Correct	0 ms	43928 KB	Output is correct
27	Correct	0 ms	43928 KB	Output is correct
28	Correct	20 ms	43932 KB	Output is correct
29	Correct	3 ms	43924 KB	Output is correct
30	Correct	8 ms	43924 KB	Output is correct
31	Correct	2 ms	43928 KB	Output is correct
32	Correct	7 ms	43932 KB	Output is correct
33	Correct	64 ms	43924 KB	Output is correct
34	Correct	186 ms	43924 KB	Output is correct
35	Correct	6 ms	43928 KB	Output is correct
36	Correct	93 ms	43928 KB	Output is correct
37	Correct	0 ms	43924 KB	Output is correct
38	Correct	50 ms	43928 KB	Output is correct
39	Correct	0 ms	43928 KB	Output is correct
40	Correct	0 ms	43932 KB	Output is correct
41	Correct	0 ms	43928 KB	Output is correct
42	Correct	0 ms	43924 KB	Output is correct

답안 #13539

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 18.0 / 18.0

Subtask #3 21.0 / 21.0

Subtask #4 47.0 / 47.0

Subtask #1
14.0 / 14.0

Subtask #2
18.0 / 18.0

Subtask #3
21.0 / 21.0

Subtask #4
47.0 / 47.0