답안 #102139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102139	2019-03-22T18:33:07 Z	MohamedAhmed0	K개의 묶음 (IZhO14_blocks)	C++14	53 / 100	1000 ms	80532 KB

blocks

#include <bits/stdc++.h>

using namespace std ;

int main()
{
	int n , k ;
	cin>>n>>k ;
	int arr[n+1] ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	int dp[n+1][k+1] ;
	int chosen[n+1][k+1] ;
	dp[0][1] = 0 ;
	for(int i = 1 ; i <= n ; ++i)
		dp[i][1] = max(arr[i] , dp[i-1][1]) , chosen[i][1] = dp[i][1];
	for(int j = 2 ; j <= k ; ++j)
	{
		stack<int>s ;
		for(int i = j ; i <= n ; ++i)
		{
			dp[i][j] = dp[i-1][j-1] + arr[i] ;
			chosen[i][j] = arr[i] ;
			while(s.size() > 0)
			{
				int idx = s.top() ;
				if(arr[idx] <= arr[i])
				{
					if(dp[idx][j] - chosen[idx][j] + max(chosen[idx][j] , arr[i]) < dp[i][j])
					{
						dp[i][j] = dp[idx][j] - chosen[idx][j] + max(chosen[idx][j] , arr[i]) ;
					}
					s.pop() ;
				}
				else
					break ;
			}
			if(s.size() > 0)
			{
				int idx = s.top() ;
				if(dp[idx][j] < dp[i][j])
				{
					dp[i][j] = dp[idx][j] ;
                    chosen[i][j] = chosen[idx][j] ;
				}
			}
			s.push(i) ;
		}
	}
	cout<<dp[n][k]<<"\n" ;
	return 0 ;
}

Subtask #1

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	4 ms	256 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	256 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct

Subtask #2

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	368 KB	Output is correct
6	Correct	3 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	256 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	256 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	256 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	3 ms	368 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	3 ms	512 KB	Output is correct

Subtask #4

0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2432 KB	Output is correct
2	Correct	26 ms	1536 KB	Output is correct
3	Correct	33 ms	3548 KB	Output is correct
4	Correct	287 ms	27644 KB	Output is correct
5	Correct	889 ms	80504 KB	Output is correct
6	Correct	41 ms	4472 KB	Output is correct
7	Correct	474 ms	37412 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	4 ms	384 KB	Output is correct
14	Correct	48 ms	8320 KB	Output is correct
15	Correct	8 ms	640 KB	Output is correct
16	Correct	16 ms	2432 KB	Output is correct
17	Correct	17 ms	1536 KB	Output is correct
18	Correct	25 ms	3584 KB	Output is correct
19	Correct	233 ms	27660 KB	Output is correct
20	Execution timed out	1025 ms	80532 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-