Submission #478902

#	Time	Username	Problem	Language	Result	Execution time	Memory
478902		arwaeystoamneg	Group Photo (JOI21_ho_t3)	Java	64 / 100	5018 ms	15828 KiB

Main

import java.util.*;
import java.io.*;
class segment_tree// "segment tree"
{
	int n;
	int[]a;
	segment_tree(int n)
	{
		this.n = n;
		a = new int[n];
	}
	void update(int i,int j)
	{
		a[i] = j;
	}
	int query(int i,int j)
	{
		int ans= 0;
		for(int k = i;k<j + 1;k++)ans += a[k];
		return ans;
	}
}
public class Main
{

	public static void main(String[]args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a= new int[n];
		for(int i = 0;i<n;i++) {a[i] = sc.nextInt();a[i]--;}
		int[]dp = new int[n + 1];
		for(int i= 0;i<n+1;i++)dp[i] = 1000000000;
		dp[n] = 0;
		for(int i= n;i>=0;i--)
		{
			int val = dp[i];
			ArrayList<Integer>b = new ArrayList<Integer>();
			for(int y:a)if(y<i)b.add(y);
			int[]idx = new int[i];
			for(int j = 0;j<i;j++)idx[b.get(j)] = j;
			segment_tree sum = new segment_tree(i);
			for(int j= i -1;j>=0;j--)
			{
				val += i - idx[j] - 1;
				val -=sum.query(0,idx[j]);
				sum.update(idx[j],1);
				dp[j] = Math.min(dp[j],val);
			}
			
		}
		System.out.println(dp[0]);
	}

}

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