Submission #982884

#	Time	Username	Problem	Language	Result	Execution time	Memory
982884		aaaaaarroz	Group Photo (JOI21_ho_t3)	C++17	100 / 100	306 ms	98548 KiB

Main

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

int main() {
	int n;
	cin>>n;
	vector<int>h(n);
	for(int i=0;i<n;i++){
        cin>>h[i];
        h[i]--;
    }
	vector<int>pos(n+1);
	for(int i=0;i<n;i++){
		pos[h[i]]=i;
	}
	
    vector<vector<int>>menor(n,vector<int>(n+1,0));
    for(int j=n-1;j>0;j--){
        for(int i=0;i<=h[j];i++){
            menor[j-1][i]=menor[j][i]+1;
        }
        for(int i=h[j]+1;i<=n;i++){
            menor[j-1][i]=menor[j][i];
        }
    }
    vector<int>dp(n+1);
    dp[0]=0;
    for(int i=1;i<=n;i++){
        dp[i]=INT_MAX;
        int temp=0;
        for(int j=i-1;j>=0;j--){
            temp+=(n-i)+menor[pos[j]][j]-2*menor[pos[j]][i];
            if((dp[j]+temp)<dp[i]){
                dp[i]=(dp[j]+temp);
            }
        }
    }
    //XD
    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