Submission #870010

#	Time	Username	Problem	Language	Result	Execution time	Memory
870010		aaron_dcoder	Group Photo (JOI21_ho_t3)	C++17	100 / 100	2879 ms	196960 KiB

Main

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e11;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
template<class T>
using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;



int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	ll N;
	cin >> N;

	
	vector<ll> H(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> H[i];
		H[i]--;
	}

	// dp[num sorted][desc chain till]
	vector<vector<ll>> dp(N,vector<ll>(N,-INFTY));

	vector<ll> currelems = H;
	vector<ll> pos(N,-1);

	for (ll i = 0; i < N; ++i)
	{
		pos[H[i]]=i;
	}

	for (ll ns = 0; ns < N; ++ns)
	{

		

		ll currcost = INFTY;
		for (ll still = 0; still < ns; ++still)
		{
			currcost = min(currcost,dp[still][ns-1]);
		}
		if (ns==0)
		{
			currcost = 0;
		}

		oset<ll> postaken;

		for (ll i = ns; i < N; ++i)
		{
			currcost+=(pos[i])-ll(postaken.size()-postaken.order_of_key(pos[i]));
			postaken.insert(pos[i]);
			dbgv(currcost);
			dp[ns][i]=currcost;
		}

		currelems.erase(currelems.begin()+pos[ns]);
		pos.assign(N,-1);
		for (ll i = 0; i < (ll)currelems.size(); ++i)
		{
			pos[currelems[i]] = i;
		}
	}

	ll outp = INFTY;
	for (ll still = 0; still < N; ++still)
	{
		outp = min(outp,dp[still][N-1]);
	}

	dbgfor (int i = 0; i < N; ++i)
	{
		dbgfor (int j = 0; j < N; ++j)
		{
			dbg(i << ":" << j << "=" << dp[i][j]);
		}
	}

	cout << outp;
}

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