oj.uz

Submission #412987

# Submission time Handle Problem Language Result Execution time Memory
412987 2021-05-27T23:08:06 Z jjj K blocks (IZhO14_blocks) C++14
14 / 100
 695 ms 332 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 695 ms 324 KB Output is correct
14 Correct 656 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 652 ms 328 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 695 ms 324 KB Output is correct
14 Correct 656 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 652 ms 328 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Incorrect 1 ms 332 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 695 ms 324 KB Output is correct
14 Correct 656 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 652 ms 328 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Incorrect 1 ms 332 KB Output isn't correct
31 Halted 0 ms 0 KB -