제출 #373071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373071		GioChkhaidze	Group Photo (JOI21_ho_t3)	C++14	100 / 100	417 ms	134656 KiB

Main

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 5005;

int n, q, a[N], inv[N][N], invr[N][N], S[N], Dp[N];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = a[i]; j <= n; ++j) {
			++S[j];
		}	
		
		for (int x = a[i] + 1; x <= n; ++x) {
			inv[a[i]][x] = S[n] - S[x - 1];
			invr[a[i]][x] = (x - a[i]) - (S[x] - S[a[i]]);
		}
	}

	ll U;
	for (int r = 1; r <= n; ++r) {
		Dp[r] = 1e9, U = 0;
		for (int l = r; l >= 1; --l) {
			U += inv[l][r + 1] + invr[l][r];
			if (Dp[r] > Dp[l - 1] + U)
				Dp[r] = Dp[l - 1] + U;
		}
	}
	
	cout << Dp[n] << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:11:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main () {
      |       ^

• 서브태스크 1: 5 / 5
• 서브태스크 2: 7 / 7
• 서브태스크 3: 32 / 32
• 서브태스크 4: 20 / 20
• 서브태스크 5: 36 / 36