记录编号	236466	评测结果	MMMMMMMMMM
题目名称	[网络流24题]魔术球问题（简化版）	最终得分	0
用户昵称	Fmuckss	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-03-14 12:41:50	内存使用	128.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 3205;
const int inf = 1e5;
int m;
class solve_flow {
private:
	struct edge {
		int to, le, ne;
		edge() { to = le = ne = 0; }
	}e[maxn*maxn];
	int head[maxn], tot;
	int s, t;
	int cur[maxn];
	int de[maxn];
	int n;
public:
	void beg() {
		memset(cur, 0, sizeof(cur));
		memset(de, 0, sizeof(de));
		memset(head, 0, sizeof(head));
		n = s = t = tot = 0;
	}
	void add_edge(int a, int b, int v) {
		++tot; e[tot].to = b;  e[tot].le = v;
		e[tot].ne = head[a]; head[a] = tot;
		++tot; e[tot].to = a; 
		e[tot].ne = head[b]; head[b] = tot;
	}
	bool bfs() {
		memset(de, 0, sizeof(de));
		memcpy(cur, head, (t+1)<<2);
		queue<int> q;
		while(!q.empty()) q.pop();
		q.push(s);
		de[s] = 1;
		while(!q.empty()) {
			int now = q.front(); q.pop();
			if(now == t) return 1;
			for(int i = head[now]; i; i = e[i].ne) {
				int to = e[i].to;
				if(de[to] || e[i].le <= 0) continue;
				de[to] = de[now]+1;
				q.push(to);
			}
		}
		return de[t];
	}
	int dfs(int now, int min_flow) {
		if(now == t) return min_flow;
		int now_flow;
		for(int &i = cur[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(de[to] != de[now]+1 || e[i].le <= 0) continue;
			now_flow = dfs(to, min(min_flow, e[i].le));
			if(!now_flow) continue;
			e[i].le -= now_flow;
			if(i & 1) e[i+1].le += now_flow;
			else e[i-1].le += now_flow;
			return now_flow;
		}
		return 0;
	}
	bool judge(int a, int b) {
		int tmp = sqrt(a+b);
		tmp *= tmp;
		return tmp == a+b;
	}
	void make_graph() {
		s = n*2+1;
		t = s+1;
		for(int i = 1; i <= n; i++) {
			for(int j = i+1; j <= n; j++) {
				if(judge(i, j)) add_edge(i, j+n ,1);
			}
		}
		for(int i = 1; i <= n; i++) {
			add_edge(s, i ,1);
			add_edge(i+n, t, 1);
		}
	} 
	int dinic(int tar) {
		beg();
		n = tar;
		make_graph();
		int tmp, ans = 0;
		while(bfs()) {
			while(tmp = dfs(s, inf)) ans += tmp;
		}
		return n-ans;
	}
}sf;
int solve() {
	int l = 1, r = 1600, mid;
	while(l <= r) {
		mid = (l+r)>>1;
		int tmp = sf.dinic(mid);
		if(tmp <= m) l = mid+1;
		else r = mid-1;
	}
	return r;
} 

int main() {
	freopen("balla.in", "r", stdin);
	freopen("balla.out", "w", stdout);
	scanf("%d", &m);
	printf("%d\n",solve());
	return 0;
}