Untitled
unknown
c_cpp
3 years ago
1.5 kB
3
Indexable
#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]); }
Editor is loading...