Submission #944174

#	Time	Username	Problem	Language	Result	Execution time	Memory
944174		Tsagana	Group Photo (JOI21_ho_t3)	C++14	100 / 100	799 ms	392652 KiB

Main

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mset multiset
#define F first
#define S second

using namespace std;

int n;
vector<vector<int > > dp(5001, vector<int >(5001, 0));
vector<vector<int > > psum(5001, vector<int >(5001, 0));

int inv(int up, int val, int p)
{
	int cnt = 0;
	cnt += psum[up][p] - psum[val - 1][p];
	cnt += psum[val - 1][n] - psum[val - 1][p];
	return cnt;
}
void solve ()
{
	cin >> n;
    vector<int > arr(n+1), pos(n+1);
    for (int i = 1; i <= n; i++)
    {
    	cin >> arr[i];
    	pos[arr[i]] = i;
    } 
    
    dp[1][1] = 0;
    psum[1][pos[1]] = 1;
    for (int i = 1; i <= n; i++) psum[1][i] += psum[1][i-1];
    for (int i = 2; i <= n; i++)
    {
		dp[i][i] = 1e9;
        for (int j = 1; j < i; j++)
        {
            dp[i][j] = dp[i - 1][j] + inv(i - 1, j, pos[i]);
            dp[i][i] = min(dp[i][i], dp[i - 1][j] + inv(i - 1, i, pos[i]));
        }
        for (int j = 1; j <= i; j++) psum[i][pos[j]]++;
        for (int j = 1; j <= n; j++) psum[i][j] += psum[i][j - 1];
    }
    int ans = 1e9;
    for (int i = 1; i <= n; i++) ans = min(ans, dp[n][i]);
    cout << ans;
}
signed main(){IOS solve(); return 0;}

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