Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
JOI 2017 Yo 4th
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <cmath>
#include <cstring>
int n, m;
int arr[100010];
int lenDp[(1<<20) + 10000];
int dp[(1 << 20) + 10000];
int sum[25][100010];
int len[25];
const int INF = 1e9;
int calcSum(int type, int st, int en) {
if(st == 0) {
return sum[type][en];
}else {
return sum[type][en] - sum[type][st - 1];
}
}
int main() {
for(int i = 0; i < sizeof(dp) / sizeof(int); ++i) {
dp[i] = INF;
lenDp[i] = INF;
}
dp[0] = 0;
lenDp[0] = 0;
std::cin >> n >> m;
for(int i = 0; i < n; ++i) {
std::cin >> arr[i];
--arr[i];
++len[arr[i]];
++sum[arr[i]][i];
}
for(int i = 0; i < m; ++i) {
for(int j = 1; j < n; ++j) {
sum[i][j] += sum[i][j - 1];
}
}
int bitMax = 1 << m;
for(int i = 0; i < bitMax; ++i) {
if(dp[i] == INF)
continue;
for(int j = 0; j < m; ++j) {
if(i & (1 << j)) {
continue;
}
int newBit = i | (1 << j);
dp[newBit] = std::min(dp[newBit], dp[i] + (len[j] - calcSum(j, lenDp[i], lenDp[i] + len[j] - 1)));
lenDp[newBit] = lenDp[i] + len[j];
}
}
std::cout << dp[bitMax - 1] << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment