Submission #22976

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
int n,m,memo[1<<20],a[100000],b[20][100000],cnt[20];
int f(int bits,int idx);
main(){
memset(memo,-1,sizeof(memo));
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
cnt[--a[i]]++;
}
for(int i=0;i<m;i++){
if(a[0]!=i)b[i][0]=1;
else b[i][0]=0;
for(int j=1;j<n;j++){
b[i][j]=b[i][j-1];
if(a[j]!=i)b[i][j]++;
}
}
cout<<f(0,0)<<endl;
}
int f(int bits,int idx){
if(idx==n)return 0;
if(memo[bits]!=-1)return memo[bits];
int sum,mn=100000;
for(int i=0;i<m;i++){
if(!(bits&(1<<i))){
sum=b[i][idx+cnt[i]-1]+f(bits|(1<<i),idx+cnt[i]);
if(idx!=0)sum-=b[i][idx-1];
if(mn>sum)mn=sum;
}
}
return memo[bits]=mn;
}

ステータス

項目 データ
問題 0595 - ぬいぐるみの整理 (Plush Toys)
ユーザー名 ei1516
投稿日時 2017-07-25 13:04:58
言語 C++11
状態 Accepted
得点 1
ソースコード長 760 Byte
最大実行時間 95 ms
最大メモリ使用量 12792 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 12 ms 6624 KB
1
2017-yo-t4-in2.txt AC 11 ms 8744 KB
2
2017-yo-t4-in3.txt AC 28 ms 10680 KB
3
2017-yo-t4-in4.txt AC 43 ms 10892 KB
4
2017-yo-t4-in5.txt AC 95 ms 12792 KB
5