Submission #413006

#	Time	Username	Problem	Language	Result	Execution time	Memory
413006		Ozy	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5051 ms	332 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl
#define debugarr(x,a,b) cout << #x << " = ["; rep(iii, a, b) cout << x[iii] << ", "; cout << "]\n"

#define MAX 5000
#define INF (1 << 30)

lli n;
lli arr[MAX+2],dp[MAX+2];

lli costo(lli ini, lli fin){
    vector<lli> nuevo;
    lli cnt, res, pos, t;

    res = 0;
    rep(i, 1, n){
        if (arr[i] >= ini && arr[i] <= fin){
            nuevo.push_back(arr[i]);
            --cnt;
            if (!cnt) break;
        }
        else if (arr[i] > fin) nuevo.push_back(arr[i]);
    }

    t = 0;
    repa(i, fin, ini){
        rep(j, t, nuevo.size() - 1) if (nuevo[j] == i){
            pos = j;
            break;
        }
        repa(j, pos, t + 1){
            swap(nuevo[j], nuevo[j - 1]);
            ++res;
        }
        ++t;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >>n;
    rep(i,1,n) {
        cin >> arr[i];
    }

    dp[0] = 0;
    rep(i,1,n) {
        dp[i] = INF;
        rep(j,0,i-1) {
            dp[i] = min(dp[i], dp[j] + costo(j + 1, i));
        }
    }

    cout << dp[n];

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int costo(long long int, long long int)':
Main.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Main.cpp:33:9: note: in expansion of macro 'rep'
   33 |         rep(j, t, nuevo.size() - 1) if (nuevo[j] == i){
      |         ^~~
Main.cpp:37:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         repa(j, pos, t + 1){
      |              ^
Main.cpp:25:13: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |             --cnt;
      |             ^~~~~

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