Submission #1145117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145117		nuutsnoynton	Group Photo (JOI21_ho_t3)	C++20	64 / 100	5094 ms	7936 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = int;
using pll = pair< ll, ll >;
const ll N = 802;
ll pd[N][N], Ind[N], d[N][N], ind[N], sum[N][N];

int main() {
	ll n, m, r, x, 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;
		sum[i][i] = ind[i];
		vector < ll > v;
		v.push_back(ind[i]);
		for (j = i + 1; j <= n; j ++) {
			sum[i][j] = sum[i][j - 1] + ind[j];
			r = lower_bound(v.begin(), v.end(), ind[j]) - v.begin();
			pd[i][j] = pd[i][j- 1] + r;
			v.push_back(ind[j]);
			sort(v.begin(), v.end());			
		}
	}
	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;
		for (j = i + 1; j <= n; j ++) {
			v.push_back(ind[j]);
	//		cout << ind[j] << "R" << endl;
			sort(v.begin(), v.end());		
			d[i ][j] = 0;
			for ( r = 0; r < v.size(); r ++) {
				d[i][j] += (abs(v[r] - (r + 1)));
			}
		}
	}
	//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:34:42: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   34 |         for(i = 1; i <= n; i ++) dp[i] = 1e18;
      |                                          ^~~~

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