結果

提出番号 2176
提出者 daleksprinter
言語 C++
提出日時 2018-10-03 19:41:11
問題名 (7)ぬいぐるみの整理 (Plush Toys)
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 14ms 106544KB
2 AC 100% 16ms 106544KB
3 WA 0% 17ms 106544KB
4 WA 0% 16ms 106544KB
5 WA 0% 24ms 106544KB
6 WA 0% 81ms 106528KB
7 WA 0% 187ms 106544KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

//macro-----------------------------------------------------------------------------------------
#define rep(i,a) for(int i=0;i<a;i++)
#define revrep(i,a,b) for(int i=a;i>b;i--)
#define int long long
#define sort(arr) sort(arr.begin(), arr.end())
#define reverse(arr) reverse(arr.begin(), arr.end())
#define elif else if

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pi;

//constant--------------------------------------------------------------------------------------
const int inf = 100100100100000;
const int mod = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//general_method--------------------------------------------------------------------------------
vector<int> cs(vector<int> arr){vector<int> ret = arr;rep(i,arr.size()){ret[i] += ret[i-1];}return ret;}
int ceil(int a, int b){if(a%b == 0) return a/b;else return a/b + 1;}
int digitlen(int i){int t = i;int count = 0;while(t){count += 1;t /= 10;}return count;}
int gcd(int a, int b){if(b== 0)return a;return gcd(b, a%b);}


//io_method-------------------------------------------------------------------------------------
int input(){int tmp;cin >> tmp;return tmp;}

void print(vi arr){
    
    rep(i,arr.size()) cout << arr[i] << " "; cout << endl;
}
void print(int n){
    cout << n << endl;
}
//main------------------------------------------------------------------------------------------

int n,m;
vi arr(100001);
vi cnt(21,0);
vvi cumsum(21, vi(100001,0));

int dp[1<<20];

int retexchng(int i, int frm, int to){
    if(frm > 0){
        return cumsum[i][to] - cumsum[i][frm-1];
    }else{
        return cumsum[i][to];
    }
}

int dfs(int s, int p, int chng){
    if(dp[s] > -1) return dp[s];

    if(s == (1<<m)-1) return chng;

    int exchng = -1;
    rep(i,m){
        if(!(s & (1<< i))){
            exchng = max(exchng, dfs(s + (1<<i), p + cnt[i], chng + retexchng(i,p, p + cnt[i]-1)));
        }
    }

    return dp[s] = exchng;

    
}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> n >> m;

    rep(i,n){
        arr[i] = input()-1;
    }

    rep(i,n){
        cnt[arr[i]]++;
    }


    cumsum[arr[0]][0] = 1;

    rep(i,m + 1){
        for(int j = 1; j < n; j++){
            if(arr[j] == i){
                cumsum[i][j] = cumsum[i][j-1] + 1;
            }else{
                cumsum[i][j] = cumsum[i][j-1];
            }
        }
    }

    memset(dp, -1, sizeof(dp));

    print(n- dfs(0, 0, 0));



    





}