Submission #10937

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
int N, M, A[100000];
int sum[20][100001];
int dp[1 << 20];
int rec(int bit, int left)
{
if(bit == (1 << M) - 1) return(0);
if(~dp[bit]) return(dp[bit]);
int ret = INF;
for(int i = 0; i < M; i++) {
if((bit >> i) & 1) continue;
int right = left + sum[i][N];
ret = min(ret, rec(bit | (1 << i), right) + sum[i][N] - (sum[i][right] - sum[i][left]));
}
return(dp[bit] = ret);
}
int main()
{
cin >> N >> M;
for(int i = 0; i < N; i++) {
cin >> A[i];
++sum[--A[i]][i + 1];
}
for(int i = 1; i <= N; i++) {
for(int j = 0; j < M; j++) {
sum[j][i] += sum[j][i - 1];
}
}
memset(dp, -1, sizeof(dp));
cout << rec(0, 0) << endl;
}

ステータス

項目 データ
問題 0595 - ぬいぐるみの整理 (Plush Toys)
ユーザー名 ei1333
投稿日時 2016-12-11 16:41:57
言語 C++11
状態 Accepted
得点 1
ソースコード長 795 Byte
最大実行時間 149 ms
最大メモリ使用量 12704 KB

セット

セット 得点 Cases
1 set1 20 / 20 *t4*1.txt
2 set2 0 / 20 *t4*2.txt
3 set3 0 / 20 *t4*3.txt
4 set4 0 / 20 *t4*4.txt
5 set5 0 / 20 *t4*5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2017-yo-t4-in1.txt AC 21 ms 8672 KB
1
2017-yo-t4-in2.txt AC 19 ms 10704 KB
2
2017-yo-t4-in3.txt AC 30 ms 10684 KB
3
2017-yo-t4-in4.txt AC 68 ms 12704 KB
4
2017-yo-t4-in5.txt AC 149 ms 12684 KB
5