Submission #851442

#	Time	Username	Problem	Language	Result	Execution time	Memory
851442		damwuan	Group Photo (JOI21_ho_t3)	C++17	100 / 100	225 ms	196184 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=5e3+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,h[maxn],dd[maxn][maxn],cnt[maxn][maxn],dp[maxn];
void sol()
{
    cin >> n;
    for1(i,1,n) cin >> h[i];
    for1(i,1,n)
    {
        for1(j,i+1,n)
        {
            if (h[i]<h[j])
            {
                cnt[h[i]][h[j]]=1;
            }
            else
            {
                dd[h[j]][h[i]]=1;

            }
        }
    }
    for1(range,3,n)
    {
        for1(i,1,n-range+1)
        {
            int j=i+range-1;
            cnt[i][j]=cnt[i][j] + cnt[i][j-1] + cnt[i+1][j] - cnt[i+1][j-1];
            //cerr<< i<<' '<<j<<' '<<cnt[i][j]<<'\n';
        }
    }
//    cerr<< cnt[1][5]<<'\n';
    for1(i,1,n)
    {
        for2(j,n,i+1)
        {
            dd[i][j]+=dd[i][j+1];
        }
    }
    //cerr<< dd[1][3]<<'\n';
    for1(j,2,n)
    {
        for2(i,j-2,1)
        {
            dd[i][j]+=dd[i+1][j];
        }
    }
    for1(i,1,n) dp[i]=inf;
    for1(i,1,n)
    {
        for1(j,1,i)
        {
            dp[i]=min(dp[i],dp[j-1]+cnt[j][i]+dd[j][i+1]);
        }
        //if (i==5) cerr<< dp[1-1]<<' '<<cnt[1][i]<<' '<<dd[1][i+1]<<'\n';
        //  cerr<< i<<' '<<dp[i]<<'\n';
    }
    cout << dp[n];

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

3 5 2 4 1
*/

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