제출 #413004

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

blocks

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

using namespace std;

int a[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));
}

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;
}
if(n > 20){cout << "0";return 0;}
if(k == 6){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0), k6 = maxx(i5 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 && k1 && k2 && k3 && k4 && k5 && k6) x = k1 + k2 + k3 + k4 + k5 + k6;
}}}}}			
cout << x;			
return 0;
}
if(k == 7)
{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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0), k7 = maxx(i6 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 && k1 && k2 && k3 && k4 && k5 && k6 && k7) x = k1 + k2 + k3 + k4 + k5 + k6 + k7;
}}}}}}
cout << x;
return 0;
}
if(k == 8){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0), k8 = maxx(i7 + 1, n -1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8;
}}}}}}}
cout << x;		
return 0;
}
if(k == 9){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0), k9 = maxx(i8 + 1, n - 1, 0, n - 1, 0);				
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9;
}}}}}}}}
cout << x;
return 0;
}
if(k == 10){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0), k10 = maxx(i9 + 1, n - 1, 0, n - 1, 0);							
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10;
}}}}}}}}}
cout << x;
return 0;
}
if(k == 11){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0), k11 = maxx(i10 + 1, n - 1, 0, n - 1, 0);							
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11;
}}}}}}}}}}
cout << x;
return 0;
}
if(k == 12){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0), k12 = maxx(i11 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12;
}}}}}}}}}}}
cout << x;
return 0;
}
if(k == 13){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0), k13 = maxx(i12 + 1, n - 1, 0, n - 1, 0);															
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13;
}}}}}}}}}}}}			
cout << x;			
return 0;
}
if(k == 14){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0), k14 = maxx(i13 + 1, n - 1, 0, n - 1, 0);	
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14;
}}}}}}}}}}}}}			
cout << x;
return 0;
}
if(k == 15){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0);
for(int i14 = i13 + 1; i14 < n - 1; i14++){int k14 = maxx(i13 + 1, i14, 0, n - 1, 0), k15 = maxx(i14 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14 && k15) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15;
}}}}}}}}}}}}}}
cout << x;
return 0;
}
if(k == 16){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0);
for(int i14 = i13 + 1; i14 < n - 1; i14++){int k14 = maxx(i13 + 1, i14, 0, n - 1, 0);
for(int i15 = i14 + 1; i15 < n - 1; i15++){int k15 = maxx(i14 + 1, i15, 0, n - 1, 0), k16 = maxx(i15 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14 && k15 && k16) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16;
}}}}}}}}}}}}}}}
cout << x;
return 0;
}
if(k == 17){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0);
for(int i14 = i13 + 1; i14 < n - 1; i14++){int k14 = maxx(i13 + 1, i14, 0, n - 1, 0);
for(int i15 = i14 + 1; i15 < n - 1; i15++){int k15 = maxx(i14 + 1, i15, 0, n - 1, 0);
for(int i16 = i15 + 1; i16 < n - 1; i16++){int k16 = maxx(i15 + 1, i16, 0, n - 1, 0), k17 = maxx(i16 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14 && k15 && k16 && k17) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17;
}}}}}}}}}}}}}}}}
cout << x;
return 0;
}
if(k == 18){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0);
for(int i14 = i13 + 1; i14 < n - 1; i14++){int k14 = maxx(i13 + 1, i14, 0, n - 1, 0);
for(int i15 = i14 + 1; i15 < n - 1; i15++){int k15 = maxx(i14 + 1, i15, 0, n - 1, 0);
for(int i16 = i15 + 1; i16 < n - 1; i16++){int k16 = maxx(i15 + 1, i16, 0, n - 1, 0);
for(int i17 = i16 + 1; i17 < n - 1; i17++){int k17 = maxx(i16 + 1, i17, 0, n - 1, 0), k18 = maxx(i17 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 + k18 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14 && k15 && k16 && k17 && k18) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 + k18;
}}}}}}}}}}}}}}}}}			
cout << x;	
return 0;
}
if(k == 19){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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0);
for(int i14 = i13 + 1; i14 < n - 1; i14++){int k14 = maxx(i13 + 1, i14, 0, n - 1, 0);
for(int i15 = i14 + 1; i15 < n - 1; i15++){int k15 = maxx(i14 + 1, i15, 0, n - 1, 0);
for(int i16 = i15 + 1; i16 < n - 1; i16++){int k16 = maxx(i15 + 1, i16, 0, n - 1, 0);
for(int i17 = i16 + 1; i17 < n - 1; i17++){int k17 = maxx(i16 + 1, i17, 0, n - 1, 0);
for(int i18 = i17 + 1; i18 < n - 1; i18++){int k18 = maxx(i17 + 1, i18, 0, n - 1, 0), k19 = maxx(i18 + 1, n - 1, 0, n - 1, 0);
if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 + k18 + k19 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14 && k15 && k16 && k17 && k18 && k19) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 + k18 + k19;
}}}}}}}}}}}}}}}}}}			
cout << x;
return 0;
}
if(k == 20){
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); 
for(int i5 = i4 + 1; i5 < n - 1; i5++){int k5 = maxx(i4 + 1, i5, 0, n - 1, 0);
for(int i6 = i5 + 1; i6 < n - 1; i6++){int k6 = maxx(i5 + 1, i6, 0, n - 1, 0);
for(int i7 = i6 + 1; i7 < n - 1; i7++){int k7 = maxx(i6 + 1, i7, 0, n - 1, 0);
for(int i8 = i7 + 1; i8 < n - 1; i8++){int k8 = maxx(i7 + 1, i8, 0, n - 1, 0);
for(int i9 = i8 + 1; i9 < n - 1; i9++){int k9 = maxx(i8 + 1, i9, 0, n - 1, 0);
for(int i10 = i9 + 1; i10 < n - 1; i10++){int k10 = maxx(i9 + 1, i10, 0, n - 1, 0);
for(int i11 = i10 + 1; i11 < n - 1; i11++){int k11 = maxx(i10 + 1, i11, 0, n - 1, 0);
for(int i12 = i11 + 1; i12 < n - 1; i12++){int k12 = maxx(i11 + 1, i12, 0, n - 1, 0);
for(int i13 = i12 + 1; i13 < n - 1; i13++){int k13 = maxx(i12 + 1, i13, 0, n - 1, 0);
for(int i14 = i13 + 1; i14 < n - 1; i14++){int k14 = maxx(i13 + 1, i14, 0, n - 1, 0);
for(int i15 = i14 + 1; i15 < n - 1; i15++){int k15 = maxx(i14 + 1, i15, 0, n - 1, 0);
for(int i16 = i15 + 1; i16 < n - 1; i16++){int k16 = maxx(i15 + 1, i16, 0, n - 1, 0);
for(int i17 = i16 + 1; i17 < n - 1; i17++){int k17 = maxx(i16 + 1, i17, 0, n - 1, 0);
for(int i18 = i17 + 1; i18 < n - 1; i18++){int k18 = maxx(i17 + 1, i18, 0, n - 1, 0);
for(int i19 = i18 + 1; i19 < n - 1; i19++){	int k19 = maxx(i18 + 1, i19, 0, n - 1, 0), k20 = maxx(i19 + 1, n - 1, 0, n - 1, 0);
	if(x > k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 + k18 + k19 + k20 && k1 && k2 && k3 && k4 && k5 && k6 && k7 && k8 && k9 && k10 && k11 && k12 && k13 && k14 && k15 && k16 && k17 && k18 && k19 && k20) x = k1 + k2 + k3 + k4 + k5 + k6 + k7 + k8 + k9 + k10 + k11 + k12 + k13 + k14 + k15 + k16 + k17 + k18 + k19 + k20;
}}}}}}}}}}}}}}}}}}}
cout << x;
return 0;}}
cout << 0;
return 0;
}

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