Submission #509062

#	Time	Username	Problem	Language	Result	Execution time	Memory
509062		ITO	Group Photo (JOI21_ho_t3)	C++11	100 / 100	552 ms	165260 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int fr[5001][5001], pa[5001][5001];
int main() {
    int n, a[5001], h, b[5001], x = 0, y, c = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h;
        a[h] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fr[i][j] = fr[i][j - 1];
            if (a[j] < a[i]) {
                fr[i][j]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        pa[i][i] = fr[i][n] - fr[i][i];
        for (int j = i + 1; j <= n; j++) {
            pa[i][j] = pa[i][j - 1] + fr[j][n] - fr[j][j] - (j - i) + (fr[j][j] - fr[j][i - 1]) * 2;
        }
    }
    for (int i = n; i > 0; i--) {
        for (int j = i; j < n; j++) {
            pa[i][n] = min(pa[i][n], pa[i][j] + pa[j + 1][n]);
        }
    }
    cout << pa[1][n] << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:6:24: warning: unused variable 'b' [-Wunused-variable]
    6 |     int n, a[5001], h, b[5001], x = 0, y, c = 0;
      |                        ^
Main.cpp:6:33: warning: unused variable 'x' [-Wunused-variable]
    6 |     int n, a[5001], h, b[5001], x = 0, y, c = 0;
      |                                 ^
Main.cpp:6:40: warning: unused variable 'y' [-Wunused-variable]
    6 |     int n, a[5001], h, b[5001], x = 0, y, c = 0;
      |                                        ^
Main.cpp:6:43: warning: unused variable 'c' [-Wunused-variable]
    6 |     int n, a[5001], h, b[5001], x = 0, y, c = 0;
      |                                           ^

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