6101번: 식당

https://www.acmicpc.net/problem/6101

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n, m, rt[201], dp[40001], pos[40001];
int main() {
    scanf("%d %d", &n, &m);
    fill(rt + 1, rt + 1 + (int)sqrt(n), 1);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        for (int j = sqrt(n); j >= 2; j--)
            if (pos[x] < rt[j])
                rt[j] = rt[j - 1];
        if (pos[x] != i - 1) rt[1] = i;
        pos[x] = i;
        dp[i] = 0x7fffffff;
        for (int j = sqrt(i); j >= 1; j--)
            dp[i] = min(dp[i], dp[rt[j] - 1] + j*j);
    }
    printf("%d", dp[n]);
    return 0;
}