here is code : CodeChef: Practical coding for everyone (updated link, sorry previous one was wrong link.)
Code
int gettot (vector<int>& F) {
int ans = 0;
for (int& i:F) if (i > 1) ans += i;
return ans;
}
int search (int k, vector<int>& a, vector<int>& F) {
if (a.size() < 2) return (k * (int)a.size());
//cout << "Called Search : " << a << '\n';
int tot = k + gettot(F);
vi diff(a.size()-1) ;
vi rightF(101), leftF = F;
int maxx = 0;
for (int i = 0; i < a.size() - 1; i++) {
rightF[a[i]] ++;
leftF[a[i]] --;
diff[i] = tot - (k + k + gettot (rightF) + gettot (leftF));
if (diff[i] > diff[maxx]) maxx = i;
}
//cout << "maxx = " << maxx << ' ' << diff[maxx] << '\n';
//cout << "No futher omptimaztions possible.\n";
if (diff[maxx] < 0) return tot;
vi sa(a.begin(), a.begin() + maxx + 1), sb(a.begin() + 1 + maxx, a.end());
vi Fa(101), Fb(101);
for (int i = 0; i < a.size(); i++) {
if (i <= maxx) Fa[a[i]]++;
else Fb[a[i]]++;
}
//cout << "splitted into : " << sa << " and " << sb << '\n';
return search(k, sa, Fa) + search (k, sb, Fb);
}
void solve() {
int n, k; cin >> n >> k;
vi a(n); for (int& i:a) cin >> i;
vi F(101);
for (int& i:a) F[i]++;
cout << search(k, a, F) << '\n';
}
im basically spillting my tables until it is optimal to get more benefit out of it.
but it is failing on subtask 1. ??