Submission #531566

#	Time	Username	Problem	Language	Result	Execution time	Memory
531566		amunduzbaev	Group Photo (JOI21_ho_t3)	C++17	100 / 100	817 ms	509340 KiB

Main

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

#define ar array
#define int long long

const int N = 5005;
int dp[N], a[N], pos[N];
int inv[N][N], is[N][N];
int pref[N][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>a[i], a[i]--, pos[a[i]] = i;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			is[i][j] = (pos[i] < pos[j]);
			if(i && j) pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
			else if(i) pref[i][j] = pref[i-1][j];
			else if(j) pref[i][j] = pref[i][j-1];
			pref[i][j] += is[i][j];
		}
	}
	
	auto get = [&](int i, int x, int j, int y){
		if(i < x) swap(i, x);
		if(j < y) swap(j, y);
		return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
	};
	
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			inv[i][j] = inv[i][j-1] + get(i, j - 1, j, j);
		}
	}
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=i;j<n;j++) cout<<inv[i][j]<<" ";
		//~ cout<<"\n";
	//~ }
	
	for(int i=n-1;~i;i--){
		dp[i] = 1e9;
		for(int j=1;i+j<=n;j++){
			dp[i] = min(dp[i], dp[i+j] + inv[i][i+j-1] + (i ? get(i, i+j-1, 0, i - 1) : 0));
		}
	}
	
	//~ for(int i=0;i<n;i++) cout<<dp[i]<<" ";
	//~ cout<<"\n";
	
	cout<<dp[0]<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:39: warning: array subscript -2 is below array bounds of 'long long int [5005]' [-Warray-bounds]
   30 |   return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
      |                            ~~~~~~~~~~~^
Main.cpp:30:96: warning: array subscript -2 is below array bounds of 'long long int [5005]' [-Warray-bounds]
   30 |   return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
      |                                                                                   ~~~~~~~~~~~~~^

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