Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.5 kB
2
Indexable
Never
#include <cstdio>
using namespace std;

const int MAXN = 1e6+5;
const int MAXA = 1e5+5;

inline int max(int a, int b){
	return (a>b)?a:b;
}
inline char readchar() {
	const int S = 1<<20; // buffer size
	static char buf[S], *p = buf, *q = buf;
	if(p == q && (q = (p=buf)+fread(buf,1,S,stdin)) == buf) 
		return EOF;
	return *p++;
}

inline int nextint() {
	int x = 0, c = readchar(), neg = false;
	while(('0' > c || c > '9') && c!='-' && c!=EOF) 
		c = readchar();
	if(c == '-') 
		neg = true, c = readchar();
	while('0' <= c && c <= '9') 
		x = x*10 + (c^'0'), c = readchar();
	if(neg) x = -x;
	return x; // returns 0 if EOF
}

int main(){
    int n, k;
	n = nextint();
	k = nextint();
	static int d[MAXN] = {0};
	static int p[MAXN] = {0};
	static int A[MAXN] = {0};
	static int L[MAXN] = {0};
    for(int i = 1; i <= n; i++)
        A[i] = nextint();

    int cover[MAXA] = {0};
    for(int i = 1, beg = 1; i <= n; i++){
        cover[A[i]]++;
        while(cover[A[i]] > 1){
            cover[A[beg]]--;
            beg++;
        }
        L[i] = beg;
    }
#ifdef debug
    for(int i = 1; i <= n; i++)
        cout << L[i] << " \n"[i==n];
#endif

    while(k--){
        for(int i = 0; i <= n; i++)
            p[i] = d[i];
        for(int i = 1; i <= n; i++)
            d[i] = max(d[i-1], p[L[i]-1] + i-L[i]+1);
    }
#ifdef debug
    for(int i = 1; i <= n; i++)
        cout << d[i] << " \n"[i==n];
#endif
	printf("%d\n", d[n]);
}