Submission #16105

ソースコード

?
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
#include<iostream>
using namespace std;
int n,m;
int dp[1<<20];
int count[20][1<<17];
int a[1<<17];
int sum[20];
main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];a[i]--;
for(int j=0;j<m;j++)count[j][i+1]=count[j][i]+(j==a[i]);
}
for(int i=0;i<m;i++)sum[i]=count[i][n];
for(int i=1;i<1<<m;i++)dp[i]=1e9;
for(int i=0;i<1<<m;i++)
{
int pos=0;
for(int j=0;j<m;j++)if(i&(1<<j))pos+=sum[j];
for(int j=0;j<m;j++)
{
if(i&(1<<j))continue;
dp[i|(1<<j)]=min(dp[i|(1<<j)],
dp[i]+sum[j]-count[j][pos+sum[j]]+count[j][pos]);
}
}
cout<<dp[(1<<m)-1]<<endl;
}

ステータス

項目 データ
問題 0595 - ぬいぐるみの整理 (Plush Toys)
ユーザー名 kotatsugame
投稿日時 2017-05-01 00:22:03
言語 C++11
状態 Accepted
得点 1
ソースコード長 610 Byte
最大実行時間 165 ms
最大メモリ使用量 15736 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 36 ms 4704 KB
1
2017-yo-t4-in2.txt AC 46 ms 6720 KB
2
2017-yo-t4-in3.txt AC 59 ms 8576 KB
3
2017-yo-t4-in4.txt AC 84 ms 13264 KB
4
2017-yo-t4-in5.txt AC 165 ms 15736 KB
5