Submission #1056703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056703		SalihSahin	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5023 ms	4188 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define double long double
using namespace std;

const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int32_t main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // dp[we put first i elements without changing order of other ones] = minimum cost to get this array
    int n;
    cin>>n;
    vector<int> a(n), dp(n+1, mod);
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    vector<int> arr[n+1];
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= a[i]; j++){
            arr[j].pb(a[i]);
        }
    }

    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        for(int pre = i-1; pre >= 0; pre--){
            // dp[i] = min(dp[i], dp[pre] + cost[i][pre]);
            int cost = 0, ind = 0;
            vector<int> sim = arr[pre + 1];
            for(int j = i; j >= pre + 1; j--){
                int possim = 0;
                for(int pos = 0; pos < sim.size(); pos++){
                    if(sim[pos] == j){
                        possim = pos;
                        break;
                    }
                }
                cost += possim - ind;
                for(int pos = possim; pos >= ind + 1; pos--) sim[pos] = sim[pos - 1];
                sim[ind] = j;
            ind++;
            }

            dp[i] = min(dp[i], dp[pre] + cost);
        }
    }

    cout<<dp[n]<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:34:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 for(int pos = 0; pos < sim.size(); pos++){
      |                                  ~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36