Submission #379555

#	Time	Username	Problem	Language	Result	Execution time	Memory
379555		socho	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1711 ms	134892 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];


int fw[MXN*2];
void update(int x, int v) {
    for (; x<MXN*2; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}

int fw2[MXN*2];
void update2(int x, int v) {
    for (; x<MXN*2; x+=x&(-x)) fw2[x] += v; 
}
int sum2(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw2[x];
    return res;
}

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;
	}
	
	memset(fw, 0, sizeof fw);
	
	for (int x=L; x<=n; x++) {
		// for each [L][x], how many inversions in this range?
		// when i add a new x, the number of inversions increases by the number of values before x and smaller than x
		// also increases by number of values after x and larger than x
		iv[L][x] = iv[L][x-1];
		// now i add item x
		// all previous items which are before it are a new inversion
		iv[L][x] += sum(pos[x]);
		update(pos[x], 1);
	}
	
	memset(fw2, 0, sizeof fw2);
	memset(fw, 0, sizeof fw);
	
	for (int i=L; i<=n; i++) {
		update2(before[i]+1, 1);
	}
	
	int tcost = 0;
	for (int i=n; i>=L; i--) {
		cost[L][i] = iv[L][i] + tcost;
		tcost -= sum(before[i]+1);
		update(before[i]+1, 1);
		update2(before[i]+1, -1);
		tcost += sum2(n) - sum2(before[i]+1);
	}
	
}

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 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: 20 / 20
• Subtask 5: 36 / 36