Submission #11039

ソースコード

?
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
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define INF (1<<30)
lld N,M;
lld doll[100010];
lld cnt[100010];
lld dp[1100000];
lld sum[21][100010];
lld solve(lld bit,lld now){
if(bit == (1<<M)-1) return 0;
if(dp[bit] != -1) return dp[bit];
lld ret = INF;
for(int i=0;i<M;i++){
if(bit&(1<<i)) continue;
lld add = cnt[i]-(sum[i][now+cnt[i]]-sum[i][now]);
ret = min(ret,solve(bit|(1<<i),now+cnt[i])+add);
}
return dp[bit] = ret;
}
int main(){
cin >> N >> M;
memset(cnt,0,sizeof(cnt));
for(int i=0;i<N;i++){
cin >> doll[i];
doll[i]--;
cnt[doll[i]]++;
}
memset(sum,0,sizeof(sum));
for(int i=0;i<M;i++){
for(int j=1;j<=N;j++){
sum[i][j] = sum[i][j-1];
if(doll[j-1] == i){
sum[i][j]++;
}
}
}
memset(dp,-1,sizeof(dp));
cout << solve(0,0) << endl;
}

ステータス

項目 データ
問題 0595 - ぬいぐるみの整理 (Plush Toys)
ユーザー名 ei1428
投稿日時 2016-12-12 15:43:16
言語 C++11
状態 Accepted
得点 1
ソースコード長 894 Byte
最大実行時間 232 ms
最大メモリ使用量 27060 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 26 ms 26208 KB
1
2017-yo-t4-in2.txt AC 31 ms 26388 KB
2
2017-yo-t4-in3.txt AC 37 ms 27060 KB
3
2017-yo-t4-in4.txt AC 59 ms 26208 KB
4
2017-yo-t4-in5.txt AC 232 ms 27000 KB
5