Submission #1091917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091917		mostafa133	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1569 ms	588532 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define vec vector
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const ll mod = 1e9 + 7;
ld fpow(ll a, ll b, ll m = -1)
{
	if (m != -1)
		a %= m;
	ll res = 1;
	while (b > 0)
	{
		if (b % 2 == 1)
		{
			if (m != -1)
				res = res * a % m;
			else
			{
				res *= a;
			}
		}
		a = a * a;
		if (m != -1)
		{
			a %= m;
		}
		b /= 2;
	}
	return res;
}
int main()
{
	// fast;
	// freopen("pails.in", "r", stdin);
	// freopen("pails.out", "w", stdout);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		ll n;
		cin >> n;
		vec<ll> v(n), a(n);
		for (int i = 0; i < n; i++)
		{
			cin >> v[i];
			v[i]--;
			a[v[i]] = i;
		}
		vec<vec<ll>> b(n, vec<ll>(n+1)), c(n, vec<ll>(n+1)), d(n, vec<ll>(n+1));
		ordered_set os;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				b[v[i]][j] = os.order_of_key(j);
			}
			os.insert(v[i]);
		}
		// b[i][j] = >j
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j <= i; j++)
			{
				c[i][j] = b[i][i] - b[i][j];
				// cout << c[i][j] << ';';
			}
			// cout << '\n';
		}
		//c[i][j] = <i&>=j
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				b[i][j] = a[i] - b[i][j];
				// cout << b[i][j] << ' ';
			}
			// cout  << '\n';
		}
		// cout << '\n';
		for (int i = 0; i < n; i++)
		{
			for (int j = 1; j < n; j++)
				b[j][i] += b[j - 1][i], c[j][i]+=c[j-1][i];
		}
		// for (int i = 0; i < n; i++)
		{
			// for (int j = 0; j < n; j++){
				// cout << b[i][j] << ' ';}
			// cout << '\n';
		}
		vec<ll> dp(n);
		for (int i = 0; i < n; i++)
		{
			dp[i] = b[i][i+1]+c[i][0];
			for (int j = 0; j < i; j++)
			{
				ll x = b[i][i+1] - (b[j][i+1])+c[i][j+1];
				dp[i] = min(dp[i], dp[j] + x);
				// cout << x << ';';
			}
			// cout << dp[i] << ' ';
		}
		cout << dp[n - 1];
	end:;
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:2: warning: label 'end' defined but not used [-Wunused-label]
  112 |  end:;
      |  ^~~

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