Submission #372513

#	Time	Username	Problem	Language	Result	Execution time	Memory
372513		Kevin_Zhang_TW	Group Photo (JOI21_ho_t3)	C++17	100 / 100	681 ms	620 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 5010;

int n, a[MAX_N];

int dp[MAX_N], pos[MAX_N], fr[MAX_N];

struct bit {
	vector<int> val;
	void add(int i) {
		for (;i <= n;i += i & -i) val[i] ++;
	}
	int qry(int i) {
		int res = 0;
		for (;i;i ^= i & -i) res += val[i];
		return res;
	}
	bit() { val.resize(n + 1); }
};


int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1;i <= n;++i)
		cin >> a[i];

	fill(dp, dp + n + 1, n * n); dp[0] = 0;

	for (int i = 0;i < n;++i) {

		bit tree;

		for (int j = 1;j <= n;++j) assert(tree.qry(j) == 0);

		int rk = 0;
		for (int j = 1;j <= n;++j) if (a[j] > i) 
			pos[ a[j] ] = ++rk;

		int cost = dp[i], ni = 0, ps = 0;

		for (int j = i + 1;j <= n;++j) {
			ni += tree.qry(pos[j]);
			ps += pos[j] - (j - i);

			if (i == 1) DE(i, j, ni, ps);

			if (chmin(dp[j], ni + ps + dp[i])) {
				fr[j] = i;
				if (i == 1) DE(ni + ps + dp[i]);
			}

			tree.add(pos[j]);
		}
	}

	cout << dp[n] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Main.cpp:62:16: note: in expansion of macro 'DE'
   62 |    if (i == 1) DE(i, j, ni, ps);
      |                ^~
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Main.cpp:66:17: note: in expansion of macro 'DE'
   66 |     if (i == 1) DE(ni + ps + dp[i]);
      |                 ^~
Main.cpp:56:7: warning: unused variable 'cost' [-Wunused-variable]
   56 |   int cost = dp[i], ni = 0, ps = 0;
      |       ^~~~

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