Submission #26015768

---

Source Code Expand

/*
    Author : SharpnessV
    Right Output ! & Accepted !
*/
#include<bits/stdc++.h>
//#include<atcoder/all>
//#define int long long

#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define pre(i, a, b) for(int i = (a);i >= (b);i--)
#define rp(i, a) for(int i = 1; i <= (a); i++)
#define pr(i, a) for(int i = (a); i >= 1; i--)
#define go(i, x) for(auto i : x)

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ze(p) memset(p, 0, sizeof(p))
#define mem(p, x) memset(p, x, sizeof(p))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define si(x) (int)(x).size()
#define db cerr
#define pc putchar
#define gc getchar
#define el putchar('\n')

using namespace std;
const double eps = 1e-15, pi = 3.1415926535897932385;
typedef long long LL;
typedef pair<int,int> Pr;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}, inf = 0x7fffffff;
//Author : SharpnessV
//#define main Solution
//char buf[1<<22],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	int x = 0;
	bool f = 1;
	char ch = gc();
	while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = gc();
	while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
	if(f)return x;
	return -x;
}
inline LL Read() {
	LL x = 0;
	bool f = 1;
	char ch = gc();
	while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = gc();
	while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
	if(f)return x;
	return -x;
}
int gcd(int x,int y) {
	return y ? gcd(y, x % y) : x;
}
int lcm(int x,int y) {
	return x / gcd(x, y) * y;
}
#define P 1000000007
//#define P 998244353
#define bas 229
inline void ad(int &x, int y) {
	x += y;
	if(x >= P) x -= P;
}
inline void su(int &x, int y) {
	x -= y;
	if(x < 0) x += P;
}
inline void cmn(int &x,int y) {
	if(y < x) x = y;
}
inline void cmx(int &x,int y) {
	if(y > x) x = y;
}
inline void cmn(LL &x, LL y) {
	if(y < x) x = y;
}
inline void cmx(LL &x, LL y) {
	if(y > x) x = y;
}

int Pow(int x, int y) {
	if(y < 0)return Pow(Pow(x, P - 2), -y);
	int now = 1 ;
	for(; y; y >>= 1, x = 1LL * x * x % P)if(y & 1) now = 1LL * now * x % P;
	return now;
}

/*******************************************************************************************************************/
/*                                                                                                                 */
/*******************************************************************************************************************/
#define N 205
#define K 16
int n, k, a[N], f[N][1 << K], g[N][1 << K], c[1 << K], u[1 << K];
int s(int l,int r){
	return (l + r) * (r - l + 1) / 2;
}
int main() {
	//int T = read();while(T--)solve();
	n = read(), k = read(); int t = (1 << k) - 1;
	rp(i, n)a[i] = read() - 1;
	rp(i, t)c[i] = c[i >> 1] + (i & 1);
	memset(f, 0x3f, sizeof(f));
	memset(g, 0x3f, sizeof(g));
	f[0][0] = g[n + 1][0] = 0;
	rp(i, n){
		rep(j, 0, t){
			f[i][j] = f[i - 1][j];
			if(1 & (j >> a[i])){
				int w = j ^ (1 << a[i]), p = (1 << a[i]) - 1;
				cmn(f[i][j], f[i - 1][w] - i + c[(w | p) ^ p]);
			}
		}
	}
	pr(i, n){
		rep(j, 0, t){
			g[i][j] = g[i + 1][j];
			if(1 & (j >> a[i])){
				int w = j ^ (1 << a[i]), p = (1 << a[i]) - 1;
				cmn(g[i][j], g[i + 1][w] + i + c[w & p]);
			}
		}
	}
	rep(i, 0, t)
		rep(j, 0, k - 1)if(1 & (i >> j))
			u[i] += c[((1 << j) - 1) & (t ^ i)];
	int ans = inf;
	rp(i, n - k + 1){
		rep(w, 0, t)
			cmn(ans, f[i + c[w] - 1][w] + g[i + c[w]][t ^ w] + u[w] + s(i, i + c[w] - 1) - s(i + c[w], i + k - 1));
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result