Submission #543758

#	Time	Username	Problem	Language	Result	Execution time	Memory
543758		Asymmetry	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5060 ms	340 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 wylicz(int l, int r) {
	int ret = 0;
	for (int i = l; i <= r; ++i) {
		// ile na lewo od wartości i jest w przedziale wartości <r + 1, n>
		for (int j = p[i] - 1; j; --j) {
			if (t[j] > r) {
				++ret;
			}
		}
		// ile na lewo od wartości i jest w przedziale wartości <l, i - 1>
		for (int j = p[i] - 1; j; --j) {
			if (l <= t[j] && t[j] < i) {
				++ret;
			}
		}
	}
	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 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:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d", &t[i]);
      |   ~~~~~^~~~~~~~~~~~~

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