제출 #381159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
381159		usachevd0	Group Photo (JOI21_ho_t3)	C++14	100 / 100	850 ms	98516 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

const int N = 5003;
int P[N], iP[N];
int sum[N][N];
int dp[N];

int gt(int x1, int x2, int y1, int y2)
{
    if (x1 > x2 || y1 > y2) return 0;
    --x1;
    --y1;
    return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> P[i];
        iP[P[i]] = i;
    }
    for (int l = 1; l <= n; ++l)
        for (int r = 1; r <= n; ++r)
            if (iP[l] > iP[r])
                sum[l][r] = 1;
    for (int x = 0; x <= n; ++x)
        for (int y = 1; y <= n; ++y)
            sum[x][y] += sum[x][y - 1];
    for (int y = 0; y <= n; ++y)
        for (int x = 1; x <= n; ++x)
            sum[x][y] += sum[x - 1][y];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        int g = 0;
        for (int p = i - 1; p >= 0; --p)
        {
            int x = i - p;
            g += gt(p + 2, p + x, p + 1, p + 1);
            chkmin(dp[i], dp[p] + gt(1, p, p + 1, p + x) + g);
        }
    }
    cout << dp[n] << '\n';
    
    return 0;
}

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