Submission #543761

#	Time	Username	Problem	Language	Result	Execution time	Memory
543761		Asymmetry	Group Photo (JOI21_ho_t3)	C++17	100 / 100	448 ms	98600 KiB

Main

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 5010;
int n;
int t[N];
int p[N];
int dp[N];
int nas[N];
int sum[N][N];

int wylicz(int l, int r) {
	int ret = 0;
	ret += sum[r][n] - sum[l - 1][n] - sum[r][r] + sum[l - 1][r];
	ret += nas[r] - nas[l - 1] - sum[r][l - 1] + sum[l - 1][l - 1];
	debug(l, r, ret);
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &t[i]);
		p[t[i]] = i;
	}
	for (int i = 1; i <= n; ++i) { // pozycja
		for (int j = 1; j < i; ++j) {
			if (t[j] < t[i]) {
				++nas[t[i]];
			}
		}
		for (int j = 1; j < i; ++j) {
			++sum[t[i]][t[j]];
		}
		for (int j = 1; j <= n; ++j) {
			sum[t[i]][j] += sum[t[i]][j - 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		nas[i] += nas[i - 1];
		for (int j = 1; j <= n; ++j) {
			sum[i][j] += sum[i - 1][j];
		}
	}
	for (int r = 1; r <= n; ++r) {
		dp[r] = 1e9;
		for (int l = r; l; --l) {
			dp[r] = min(dp[r], dp[l - 1] + wylicz(l, r));
		}
	}
	printf("%d\n", dp[n]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", &t[i]);
      |   ~~~~~^~~~~~~~~~~~~

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