제출 #1315821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315821		WH8	Group Photo (JOI21_ho_t3)	C++20	100 / 100	630 ms	196636 KiB

Main

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iiii tuple<int, int,int,int>
#define ld long double
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int maxn=5005;
int fw[3][maxn];
void upd(int t, int x, int v){
	while(x <= maxn){
		fw[t][x]+=v;
		x+=(x&(-x));
	}
}
int qry(int t, int x){
	int ret=0;
	while(x > 0){
		ret += fw[t][x];
		x-=(x&(-x));
	}
	return ret;
}
signed main(){
	int n;cin>>n;
	vector<int> v(n+1), pos(n+1); for(int i=1;i<=n;i++){
		cin>>v[i];
		pos[v[i]]=i;
	}
	vector<vector<int>> cost(n+1, vector<int>(n+1, 0));
	for(int i=1;i<=n;i++){
		upd(1, i, 1);
	}
	/*cout<<pos[1]<<endl;
	cout<<qry(1, pos[1]-1);
	return 0;*/
	vector<int> rb;
	for(int j=1;j<=n;j++){
		for(auto it: rb){
			upd(2, it, -1);
		}
		rb.clear();
		int cc=0;
		for(int i=j;i<=n;i++){
			int minus=qry(2, maxn) - qry(2, pos[i]);
			int mv=qry(1, pos[i]-1);
			cc += mv - minus;
			upd(2, pos[i], 1);
			rb.pb(pos[i]);
			cost[j][i] = cc;
			//printf("cost of %lld to %lld is %lld,mv %lld minused %lld\n", j, i, cc, mv, minus);
		}
		upd(1, pos[j], -1);
		//if(j==1)break;
	}
	vector<int> dp(n+1, 1e9);
	dp[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i]=min(dp[i], dp[j-1] + cost[j][i]);
		}
	}
	cout<<dp[n];
}

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