제출 #412987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412987		jjj	K개의 묶음 (IZhO14_blocks)	C++14	14 / 100	695 ms	332 KiB

blocks

#include <bits/stdc++.h>
#define MAXN 1000010

using namespace std;

int a[MAXN], m[MAXN], seg[4 * MAXN];

void konstruisi(int i, int l, int r)
{
	if(l == r) seg[i] = a[l];
	else
	{
		konstruisi(2 * i + 1, l, (l + r) / 2);
		konstruisi(2 * i + 2, (l + r) / 2 + 1, r);
		
		seg[i] = max(seg[2 * i + 1], seg[2 * i + 2]); 
	}
}

void update(int i, int p, int x, int l, int r)
{
	if(l == r) seg[i] = x;
	else
	{
		if(p <= (l + r) / 2) update(2 * i + 1, p, x, l, (l + r) / 2);
		else update(2 * i + 2, p, x, (l + r) / 2 + 1, r);
		
		seg[i] = max(seg[2 * i + 1], seg[2 * i + 2]);
	}
}

int maxx(int tl, int tr, int l, int r, int i)
{
	if(tl == l && tr == r) return seg[i];	
	if(tl > tr) return 0;
	
//	if(tl <= l && r >= tr)
	 return max(maxx(tl, min(tr, (l + r) / 2), l, (l + r) / 2, 2 * i + 1), maxx(max(tl, (l + r) / 2 + 1), tr, (l + r) / 2 + 1, r, 2 * i + 2));
}

/*
void mesta(int n, int k, int c)
{
	if(c == k - 1)
	{
		int z = 0;
		
		for(int i = 0; i < k; i++)
			z += x = maxx(m[i], m[i + 1] - 1);
		
		if(z < s) s = z;
	}
	else
	{
		if(m[c] < k - c)
	}
}
*/
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n, k;
	
	cin >> n >> k;
	
	for(int i = 0; i < n; i++) cin >> a[i];
	
	konstruisi(0, 0, n - 1);
		
	if(n <= 100 && k <= 20 && (n <= 20 || k <= 5))
	{
		if(k == 1)
		{
			cout << maxx(0, n - 1, 0, n - 1, 0);
			
			return 0;
		}
		if(k == 2)
		{
			int x = 1e9;
			
			for(int i = 0; i < n - 1; i++)
			{
				int k1 = maxx(0, i, 0, n - 1, 0), k2 = maxx(i + 1, n - 1, 0, n - 1, 0);
				
				if(k1 + k2 < x && k1 && k2) x = k1 + k2;
			}
			
			cout << x;
			
			return 0;
		}
		if(k == 3)
		{
			int x = 1e9;
			
			for(int i1 = 0; i1 < n - 1; i1++)
			{
				int k1 = maxx(0, i1, 0, n - 1, 0);
				
				for(int i2 = i1 + 1; i2 < n - 1; i2++)
				{
					int k2 = maxx(i1 + 1, i2, 0, n - 1, 0), k3 = maxx(i2 + 1, n - 1, 0, n - 1, 0);
					
					if(x > k1 + k2 + k3 && k1 && k2 && k3) x = k1 + k2 + k3;
				}
			}
			
			cout << x;
			
			return 0;
		}
		if(k == 4)
		{
			int x = 1e9;
			
			for(int i1 = 0; i1 < n - 1; i1++)
			{
				int k1 = maxx(0, i1, 0, n - 1, 0);
				
				for(int i2 = i1 + 1; i2 < n - 1; i2++)
				{
					int k2 = maxx(i1 + 1, i2, 0, n - 1, 0);
					
					for(int i3 = i2 + 1; i2 < n - 1; i2++)
					{
						int k3 = maxx(i2 + 1, i3, 0, n - 1, 0), k4 = maxx(i3 + 1, n - 1, 0, n - 1, 0);
						
						if(k1 + k2 + k3 + k4 < x && k1 && k2 && k3 && k4) x = k1 + k2 + k3 + k4;
					}
				}
			}
			
			cout << x;
			
			return 0;
		}
		if(k == 5)
		{
			int x = 1e9;
			
			for(int i1 = 0; i1 < n - 1; i1++)
			{
				int k1 = maxx(0, i1, 0, n - 1, 0);
				
				for(int i2 = i1 + 1; i2 < n - 1; i2++)
				{
					int k2 = maxx(i1 + 1, i2, 0, n - 1, 0);
					
					for(int i3 = i2 + 1; i3 < n - 1; i3++)
					{
						int k3 = maxx(i2 + 1, i3, 0, n - 1, 0);
						
						for(int i4 = i3 + 1; i4 < n - 1; i4++)
						{
							int k4 = maxx(i3 + 1, i4, 0, n - 1, 0), k5 = maxx(i4 + 1, n - 1, 0, n - 1, 0);
							
							if(x > k1 + k2 + k3 + k4 + k5 && k1 && k2 && k3 && k4 && k5) x = k1 + k2 + k3 + k4 + k5;
						}
					}
				}
			}
			
			cout << x;
			
			return 0;
		}
	}
	
	cout << 0;
	
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47