oj.uz

Submission #856880

# Submission time Handle Problem Language Result Execution time Memory
856880 2023-10-04T18:45:57 Z StefanSebez Group Photo (JOI21_ho_t3) C++14
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5050;
int lc[2*N],rc[2*N],sum[2*N],nc,root;
void Update(int &c,int ss,int se,int qind,int qval)
{
	if(!c) c=++nc;
	if(ss==se) {sum[c]=qval;return;}
	int mid=(ss+se)/2;
	if(qind<=mid) Update(lc[c],ss,mid,qind,qval);
	else Update(rc[c],mid+1,se,qind,qval);
	sum[c]=sum[lc[c]]+sum[rc[c]];
}
int Get(int c,int ss,int se,int qs,int qe)
{
	if(qs<=ss && se<=qe) return sum[c];
	else if(qe<ss || se<qs) return 0;
	int mid=(ss+se)/2;
	return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}
signed main()
{
    int n;cin>>n;
    int a[n+1],ind[n+1];for(int i=1;i<=n;i++){cin>>a[i];ind[a[i]]=i;}
    int dp[n+50];
    dp[n+1]=0;
    for(int i=n;i>=1;i--)
	{
		int s=0,b[n+1]={0};
		for(int j=i;j<=n;j++)
		{
			Update(root,1,n,ind[j],1);
		}
		for(int j=i;j<=n;j++)
		{
			b[j]=Get(root,1,n,1,ind[j])-1;
		}
		for(int j=i;j<=n;j++)
		{
			Update(root,1,n,ind[j],0);
		}
		for(int j=i;j<=n;j++)
		{
			int k=ind[j],x=Get(root,1,n,k,n);
			s-=x;
			s+=b[j];
			dp[i]=min(dp[i],dp[j+1]+s);
			Update(root,1,n,k,1);
		}
		for(int j=i;j<=n;j++)
		{
			Update(root,1,n,ind[j],0);
		}
	}
	cout<<dp[1]<<endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -