Submission #752945

#	Time	Username	Problem	Language	Result	Execution time	Memory
752945		IvanJ	Group Photo (JOI21_ho_t3)	C++17	100 / 100	587 ms	160816 KiB

Main

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e3 + 5;

int n, ans = 0;
int h[maxn];
int dp[maxn];

int solve(int N) {
	if(N < 2) return 0;
	if(dp[N] != -1) return dp[N];
	
	vector<int> v;
	for(int i = 0;i < n;i++) 
		if(h[i] <= N) v.pb(h[i]);
	
	vector<int> pos(N + 1, 0);
	for(int i = 0;i < N;i++) pos[v[i]] = i;
	
	int ret = 1e9;
	int cost = 0;
	vector<int> fwt(N + 1, 0);
	for(int i = N;i >= 1;i--) {
		cost += i - pos[i] - 1;
		{
			for(int x = N;x > 0;x -= (x & -x)) cost += fwt[x];
			for(int x = pos[i] + 1;x > 0;x -= (x & -x)) cost -= fwt[x];
			for(int x = pos[i] + 1;x <= N;x += (x & -x)) fwt[x]++; 	
		}
		//cout << i << " " << cost << "\n";
		//cout << N << " " << i << " " << solve(i - 1) << " " << cost << "\n";
		ret = min(ret, solve(i - 1) + cost);
	}
	return dp[N] = ret;
}

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d", h + i);
	
	memset(dp, -1, sizeof dp);
	ans = solve(n);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

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