Submission #720025

#	Time	Username	Problem	Language	Result	Execution time	Memory
720025		khanhhdz191	Group Photo (JOI21_ho_t3)	C++14	100 / 100	423 ms	196352 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=  5002;
const ll base=3e18;
const ll mod= 1e9+7 ;
/// goal 4/8
ll pos[maxn];
ll dp[maxn];
ll sum[maxn][maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("cheetos.inp","r"))
    {
        freopen("cheetos.in","r",stdin);
        freopen("cheetos.out","w",stdout);
    }
     ll n;
     cin>> n;
     for (int i=1; i<=n; i++)
     {
        ll x;
        cin>> x;
        pos[x]=i;
     }
    ll ans=0;
    for (int i=1; i<=n; i++)
    for (int j=1; j<i; j++)
    {
       if (pos[j]>pos[i]) ans++;
    }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
        {
            if (i<j&&pos[i]>pos[j]) sum[i][j]--;
            if (i<j&&pos[i]<pos[j]) sum[i][j]++;
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    for (int i=1; i<=n; i++)
    {
        dp[i]=base;
        for (int j=0; j<i; j++)
        {
            dp[i]=min(dp[i],dp[j]+sum[i][i]+sum[j][j]-sum[i][j]-sum[j][i]);
        }
    }
    ans+=dp[n];
    cout <<ans;


}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("cheetos.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("cheetos.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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