Submission #602237

#	Time	Username	Problem	Language	Result	Execution time	Memory
602237		SamAnd	Group Photo (JOI21_ho_t3)	C++17	100 / 100	647 ms	196336 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 5003;

void por()
{
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 1; i <= n; ++i)
        v.push_back(i);

    do
    {
        bool z = true;
        for (int i = 0; i < n - 1; ++i)
        {
            if (v[i] >= v[i + 1] + 2)
            {
                z = false;
                break;
            }
        }
        if (z)
        {
            for (int i = 0; i < n; ++i)
                cout << v[i] << ' ';
            cout << "\n";
        }
    } while (next_permutation(all(v)));
}

int n;
int a[N];

int b[N];
int l[N][N], r[N][N];

int dp[N];

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        memset(b, 0, sizeof b);
        for (int j = 1; j < i; ++j)
            b[a[j]]++;
        for (int j = 1; j <= n; ++j)
            l[a[i]][j] = l[a[i]][j - 1] + b[j];

        memset(b, 0, sizeof b);
        for (int j = i + 1; j <= n; ++j)
            b[a[j]]++;
        for (int j = 1; j <= n; ++j)
            r[a[i]][j] = r[a[i]][j - 1] + b[j];
    }

    for (int x = 1; x <= n; ++x)
    {
        int s = l[x][n] - l[x][x];
        dp[x] = dp[x - 1] + s;
        for (int y = x - 1; y >= 1; --y)
        {
            s += l[y][n] - l[y][x];
            s += r[y][x] - r[y][y];
            dp[x] = min(dp[x], dp[y - 1] + s);
        }
    }

    cout << dp[n] << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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