Submission #379549

#	Time	Username	Problem	Language	Result	Execution time	Memory
379549		socho	Group Photo (JOI21_ho_t3)	C++14	44 / 100	5037 ms	2312 KiB

Main

// upsolve, inspired by @smjleo code
#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
// #define endl '\n'
// #define double long double
// #define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;

const int MXN = 5005;
int n;
int arr[MXN];
int pos[MXN];
int dp[MXN];
vector<int> rgs;

int cost[MXN][MXN];
int iv[MXN][MXN];
int before[MXN];
int herepos[MXN];

void solverow(int L) {
	
	// only values >= L exist
	
	// find all cost[L][x]
	
	int curr = 0;
	for (auto x: rgs) {
		before[x] = curr;
		curr++;
		herepos[x] = curr;
	}
	
	for (int x=L; x<=n; x++) {
		// solve [L][x]
		int inv = 0;
		// in the values from L..x, how many inversions
		for (int i=1; i<=n; i++) {
			for (int j=i+1; j<=n; j++) {
				if (L <= arr[i] && arr[i] <= x && L <= arr[j] && arr[j] <= x && arr[i] < arr[j]) inv++;
			}
		}
		iv[L][x] = inv;
	}
	
	int tcost = 0;
	for (int i=n; i>=L; i--) {
		cost[L][i] = iv[L][i] + tcost;
		for (int x=before[i]; x<rgs.size(); x++) {
			if (rgs[x] < i) tcost++;
		}
		for (int x=before[i]; x>=0; x--) {
			if (rgs[x] > i) tcost--;
		}
	}
	
}

signed main() {

	ran(); fast();

	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> arr[i];
		pos[arr[i]] = i;
	}
	
	for (int i=1; i<=n; i++) {
		rgs.clear();
		for (int j=1; j<=n; j++) {
			if (arr[j] >= i) rgs.push_back(arr[j]);
		}
		solverow(i);
	}

	for (int i=1; i<=n; i++) {
		
		// solve first i positions
		dp[i] = INT_MAX / 2;
		
		for (int j=1; j<=i; j++) {
			
			// j..i are in reverse, + dp[j-1]
			dp[i] = min(dp[i], dp[j-1] + cost[j][i]);
			
		}
		
	}
	
	cout << dp[n] << endl;

}

Compilation message (stderr)

Main.cpp: In function 'void solverow(int)':
Main.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int x=before[i]; x<rgs.size(); x++) {
      |                         ~^~~~~~~~~~~
Main.cpp: In function 'void usaco()':
Main.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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