Submission #70487841

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 7;
const int M = 507;
const int inf = 1e9 + 7;
const int S = 2e4 + 7;
int n;
int a[N], tot;
bitset<M*M/2>bs[M];
bool B[N];
int dp[M * M / 2], ndp[M * M / 2];
int ans;
void Main(){
	ans = inf;
	cin >> n;
	tot = 0;
	L(i, 1, n * (n - 1) / 2) {
		int x;
		cin >> x;
		if(x){
			++tot;
			a[tot] = i - tot;
		}
	}
	if(bs[n][tot]) {
		cout << 0 << '\n';
		return;
	}
	L(x, 1, n) {
		L(y, 1, n - x) {
			int ls = n - x - y;
			int c = x + y;
			L(s, x * y - max(x, y), x * y) if(tot >= c * (c - 1) / 2 - s && bs[ls][tot - c * (c - 1) / 2 + s]) { // residual
				int ret = 0;
				L(i, 1, x * y - s)
					ret += max(s - a[tot - i + 1], 0);
				ans = min(ans, ret);
			}
		}
	}

	cout << ans << '\n';
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	bs[0].set(0);
	L(i, 1, 500) {
		L(j, 0, i - 1) {
			bs[i] |= bs[j] << ((i - j) * (i - j - 1) / 2);
		}
	}
	int t; cin >> t; while(t--) Main();
	return 0;
}

Submission Info

Judge Result