답안 #91540 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91540	2018-12-28T07:57:44 Z	Nordway	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	365 ms	48352 KB

blocks

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define boost ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

const int INF = INT_MAX;
const int mod = 998244353;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int N = 2e5+5;
const int M = 1e2+1;

int a[N],dp[N][M];

int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][1]=max(dp[i-1][1],a[i]);
	}
	for(int j=2;j<=k;j++){
		stack<pii>s;
		for(int i=j;i<=n;i++){
			int mn=dp[i-1][j-1];
			while(!s.empty()){
				if(a[s.top().x]>a[i])break;
				mn=min(mn,s.top().y);
				s.pop();
			}
			dp[i][j]=min(mn+a[i],!s.empty()?dp[s.top().x][j]:INF);
			s.push(mp(i,mn));
		}
	}
	cout<<dp[n][k];
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	500 KB	Output is correct
6	Correct	2 ms	552 KB	Output is correct
7	Correct	2 ms	556 KB	Output is correct
8	Correct	2 ms	560 KB	Output is correct
9	Correct	2 ms	568 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	2 ms	628 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	664 KB	Output is correct
14	Correct	2 ms	684 KB	Output is correct
15	Correct	2 ms	688 KB	Output is correct
16	Correct	2 ms	692 KB	Output is correct
17	Correct	2 ms	696 KB	Output is correct
18	Correct	2 ms	700 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	704 KB	Output is correct
2	Correct	2 ms	708 KB	Output is correct
3	Correct	2 ms	712 KB	Output is correct
4	Correct	2 ms	712 KB	Output is correct
5	Correct	2 ms	720 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	724 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	724 KB	Output is correct
10	Correct	2 ms	724 KB	Output is correct
11	Correct	2 ms	724 KB	Output is correct
12	Correct	2 ms	724 KB	Output is correct
13	Correct	2 ms	728 KB	Output is correct
14	Correct	2 ms	732 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	2 ms	740 KB	Output is correct
17	Correct	2 ms	744 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Correct	2 ms	752 KB	Output is correct
20	Correct	2 ms	756 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	756 KB	Output is correct
2	Correct	2 ms	756 KB	Output is correct
3	Correct	2 ms	760 KB	Output is correct
4	Correct	2 ms	764 KB	Output is correct
5	Correct	2 ms	768 KB	Output is correct
6	Correct	2 ms	772 KB	Output is correct
7	Correct	2 ms	776 KB	Output is correct
8	Correct	2 ms	780 KB	Output is correct
9	Correct	2 ms	784 KB	Output is correct
10	Correct	2 ms	788 KB	Output is correct
11	Correct	2 ms	792 KB	Output is correct
12	Correct	2 ms	796 KB	Output is correct
13	Correct	2 ms	800 KB	Output is correct
14	Correct	2 ms	804 KB	Output is correct
15	Correct	2 ms	808 KB	Output is correct
16	Correct	2 ms	808 KB	Output is correct
17	Correct	3 ms	812 KB	Output is correct
18	Correct	2 ms	812 KB	Output is correct
19	Correct	2 ms	812 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	4776 KB	Output is correct
2	Correct	63 ms	18856 KB	Output is correct
3	Correct	30 ms	19084 KB	Output is correct
4	Correct	132 ms	19488 KB	Output is correct
5	Correct	206 ms	42380 KB	Output is correct
6	Correct	61 ms	42952 KB	Output is correct
7	Correct	123 ms	43664 KB	Output is correct
8	Correct	2 ms	43664 KB	Output is correct
9	Correct	2 ms	43664 KB	Output is correct
10	Correct	2 ms	43664 KB	Output is correct
11	Correct	2 ms	43664 KB	Output is correct
12	Correct	2 ms	43664 KB	Output is correct
13	Correct	2 ms	43664 KB	Output is correct
14	Correct	25 ms	43664 KB	Output is correct
15	Correct	7 ms	43664 KB	Output is correct
16	Correct	11 ms	43664 KB	Output is correct
17	Correct	26 ms	43664 KB	Output is correct
18	Correct	31 ms	43664 KB	Output is correct
19	Correct	92 ms	43664 KB	Output is correct
20	Correct	365 ms	45592 KB	Output is correct
21	Correct	69 ms	46132 KB	Output is correct
22	Correct	149 ms	46828 KB	Output is correct
23	Correct	58 ms	47484 KB	Output is correct
24	Correct	90 ms	48132 KB	Output is correct
25	Correct	262 ms	48132 KB	Output is correct
26	Correct	2 ms	48132 KB	Output is correct
27	Correct	2 ms	48132 KB	Output is correct
28	Correct	18 ms	48132 KB	Output is correct
29	Correct	8 ms	48132 KB	Output is correct
30	Correct	10 ms	48132 KB	Output is correct
31	Correct	26 ms	48132 KB	Output is correct
32	Correct	30 ms	48132 KB	Output is correct
33	Correct	87 ms	48132 KB	Output is correct
34	Correct	210 ms	48344 KB	Output is correct
35	Correct	61 ms	48344 KB	Output is correct
36	Correct	133 ms	48352 KB	Output is correct
37	Correct	7 ms	48352 KB	Output is correct
38	Correct	17 ms	48352 KB	Output is correct
39	Correct	2 ms	48352 KB	Output is correct
40	Correct	2 ms	48352 KB	Output is correct
41	Correct	2 ms	48352 KB	Output is correct
42	Correct	2 ms	48352 KB	Output is correct

답안 #91540

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