Submission #1145855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145855		nuutsnoynton	Group Photo (JOI21_ho_t3)	C++20	100 / 100	2347 ms	134588 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = int;
using pll = pair< ll, ll >;
const ll N = 5004;
ll pd[N][N], Ind[N], d[N][N], ind[N], T[4 * N];
void Update(ll p, ll lo, ll hi, ll x) {
	if (lo == hi) {
		T[p] ++;
		return ;
	}
	ll mid = (lo + hi)/2;
	if ( x <= mid) Update(2 * p, lo, mid, x);
	else Update(2 * p + 1, mid + 1, hi, x);
	T[p]= T[2 * p] + T[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll l, ll r) {
	if ( lo > r || l > hi) return 0;
	if ( l <= lo && hi <= r) return T[p];
	ll mid = (lo + hi)/2;
	return Find(2 * p, lo, mid, l, r) + Find(2 * p + 1, mid + 1, hi, l, r);
}
int main() {
	ll n, m, r, x, sm ,hvt_cnt, s, bos_cnt, y, found, i, j, ans, t, here;
	
	cin >> n;
	
	ll dp[n + 2], a[n+ 2];
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		Ind[a[i]] = i;
		ind[a[i]] = i;
	}
	for (i = 1; i <= n; i ++) {
		pd[i][i] = 0;
		for (j = 1; j<= 4 * N; j++) T[j] = 0; 
		Update(1, 1, n, ind[i]);
		for (j = i + 1; j <= n; j ++) {
			r = Find(1, 1, n, 1, ind[j]);
			Update(1, 1, n, ind[j]);
			pd[i][j] = pd[i][j- 1] + r;
		}
	}
	for(i = 1; i <= n; i ++) dp[i] = 1e18;
//	for (i = 1; i <= n; i ++) {
//		for (j = i; j <= n; j ++) {
//			cout << i << " " << j << " " << pd[i][j] << endl;
//		}
//	}
	Ind[0] = n + 1;
	for (i = 0; i <= n; i ++) {
//		cout << i << endl;
//		for (j = i; j <= n; j ++) {
//			cout << ind[j] << " ";
//		}
//		cout << endl;
		for (r = Ind[i] + 1; r <= n; r ++) {
			ind[a[r]] --;
		}
		vector < ll > v;
		sm = 0;
		for (j = i + 1; j <= n; j ++) {
			sm += ind[j];
	//		cout << ind[j] << "R" << endl;
			d[i ][j] = 0;
			s = (j - i);
			s = s * (s + 1)/2;
			d[i][j] = sm - s;
		}
	}
	//cout << "HI" << endl;
//	for (i = 0; i <= n; i ++) {
//		for (j = i + 1; j <= n; j ++) {
//			cout << i << " " << j << " " << d[i][j] << endl;
//		}
//	}
	for (i = 1; i <= n; i ++) ind[a[i]] = i;
	dp[0]= 0;
	dp[1] = ind[1] - 1;
	for (i = 2; i <= n; i ++) {
		for (j = 0; j < i; j ++) {
			s = dp[j];
			s = s + d[j][i];
	//		cout << s << endl;
			s = s + pd[j + 1][i];
	//		cout << j << " " << dp[j] << " " << s << " " << i << endl;
			dp[i] = min(dp[i], s);
		}
//		cout << dp[i] << " " << i << endl;
	}
//	cout << endl;
//	for (i = 1; i <= n; i ++) {
//		cout << dp[i] << " ";
//	}
//	cout <<endl;
	cout << dp[n] << endl;
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:46:42: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   46 |         for(i = 1; i <= n; i ++) dp[i] = 1e18;
      |                                          ^~~~
Main.cpp:38:50: warning: iteration 20015 invokes undefined behavior [-Waggressive-loop-optimizations]
   38 |                 for (j = 1; j<= 4 * N; j++) T[j] = 0;
      |                                             ~~~~~^~~
Main.cpp:38:30: note: within this loop
   38 |                 for (j = 1; j<= 4 * N; j++) T[j] = 0;
      |                             ~^~~~~~~~
Main.cpp:38:50: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 80064 bytes into a region of size 80060 overflows the destination [-Wstringop-overflow=]
   38 |                 for (j = 1; j<= 4 * N; j++) T[j] = 0;
      |                                             ~~~~~^~~
Main.cpp:7:39: note: at offset 4 into destination object 'T' of size 80064
    7 | ll pd[N][N], Ind[N], d[N][N], ind[N], T[4 * N];
      |                                       ^

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