Japan Alumni Group Summer Camp 2013 Warming Up

Submission #478188

Source codeソースコード

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define SIZE 210
#define INF 1000000000

using namespace std;

struct MaxFlow
{
	struct edge
	{
		int to,cap,rev;
		edge(int t,int c,int r)
		{
			to=t;
			cap=c;
			rev=r;
		}
	};
	vector <edge> vec[SIZE];
	bool use[SIZE];
	
	void init()
	{
		for(int i=0;i<SIZE;i++)
		{
			vec[i].clear();
		}
	}
	void add(int start,int end,int cap)
	{
		int s=vec[start].size(),e=vec[end].size();
		vec[start].push_back(edge(end,cap,e));
		vec[end].push_back(edge(start,0,s));
	}
	int dfs(int v,int t,int f)
	{
		if(v==t) return f;
		use[v]=true;
		for(int i=0;i<vec[v].size();i++)
		{
			edge &e=vec[v][i];
			if(!use[e.to]&&e.cap>0)
			{
				int d=dfs(e.to,t,min(f,e.cap));
				if(d>0)
				{
					e.cap-=d;
					vec[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s,int t)
	{
		int flow=0;
		while(1)
		{
			memset(use,false,sizeof(use));
			int f=dfs(s,t,INF);
			if(f==0) return flow;
			flow+=f;
		}
	}
};
MaxFlow solve;
int mp[SIZE][SIZE];
int f[SIZE],s[SIZE];

int main()
{
	int h,w;
	scanf("%d %d",&h,&w);
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			scanf("%d",&mp[i][j]);
		}
	}
	for(int i=0;i<w;i++) scanf("%d",&f[i]);
	for(int i=0;i<h;i++) scanf("%d",&s[i]);
	int ret=0;
	for(int i=0;i<w;i++) ret+=max(f[i]-1,0);
	for(int i=0;i<h;i++) ret+=max(s[i]-1,0);
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			ret+=mp[i][j];
			if(mp[i][j]==1&&(f[j]==0||s[i]==0))
			{
				puts("-1");
				return 0;
			}
		}
	}
	for(int k=SIZE;k>=1;k--)
	{
		vector <int> vw,vh;
		for(int i=0;i<w;i++) if(f[i]==k) vw.push_back(i);
		for(int i=0;i<h;i++) if(s[i]==k) vh.push_back(i);
		if(vw.empty()&&vh.empty()) continue;
		int S=vw.size()+vh.size(),T=S+1;
		solve.init();
		for(int i=0;i<vh.size();i++)
		{
			for(int j=0;j<vw.size();j++)
			{
				int x=vh[i],y=vw[j];
				if(mp[x][y]==1)
				{
					solve.add(i,j+vh.size(),1);
				}
			}
		}
		for(int i=0;i<vh.size();i++)
		{
			int x=vh[i];
			bool up=false;
			for(int j=0;j<w;j++)
			{
				if(f[j]>=k&&mp[x][j]==1)
				{
					up=true;
					break;
				}
			}
			if(!up)
			{
				puts("-1");
				return 0;
			}
		}
		for(int i=0;i<vw.size();i++)
		{
			int y=vw[i];
			bool up=false;
			for(int j=0;j<h;j++)
			{
				if(s[j]>=k&&mp[j][y]==1)
				{
					up=true;
					break;
				}
			}
			if(!up)
			{
				puts("-1");
				return 0;
			}
		}
		for(int i=0;i<vh.size();i++) solve.add(S,i,1);
		for(int i=0;i<vw.size();i++) solve.add(i+vh.size(),T,1);
		int gt=solve.max_flow(S,T);
		ret-=gt*(k-1);
	}
	printf("%d\n",ret);
	return 0;
}

Submission

Task問題 C - Containers
User nameユーザ名 yutaka1999
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 AC
Score得点 100
Source lengthソースコード長 2791 Byte
File nameファイル名
Exec time実行時間 32 ms
Memory usageメモリ使用量 1056 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:79: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:84: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:87: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:88: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,6,7,8,9

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1 AC 32 ms 872 KB
10 AC 25 ms 928 KB
11 AC 26 ms 864 KB
12 AC 28 ms 872 KB
13 AC 28 ms 808 KB
14 AC 25 ms 924 KB
15 AC 25 ms 924 KB
16 AC 25 ms 924 KB
17 AC 26 ms 920 KB
18 AC 25 ms 928 KB
19 AC 24 ms 848 KB
2 AC 25 ms 928 KB
20 AC 25 ms 876 KB
21 AC 26 ms 880 KB
22 AC 27 ms 924 KB
23 AC 28 ms 944 KB
24 AC 30 ms 932 KB
25 AC 28 ms 868 KB
26 AC 28 ms 1056 KB
27 AC 27 ms 920 KB
28 AC 28 ms 1000 KB
29 AC 30 ms 876 KB
3 AC 25 ms 924 KB
30 AC 24 ms 804 KB
31 AC 26 ms 932 KB
32 AC 25 ms 928 KB
33 AC 26 ms 932 KB
34 AC 26 ms 876 KB
35 AC 25 ms 928 KB
36 AC 26 ms 920 KB
37 AC 24 ms 876 KB
38 AC 25 ms 924 KB
39 AC 26 ms 864 KB
4 AC 25 ms 920 KB
40 AC 23 ms 924 KB
41 AC 25 ms 928 KB
42 AC 25 ms 932 KB
43 AC 25 ms 928 KB
44 AC 25 ms 928 KB
45 AC 25 ms 924 KB
46 AC 25 ms 924 KB
47 AC 24 ms 928 KB
48 AC 24 ms 876 KB
49 AC 25 ms 932 KB
5 AC 25 ms 800 KB
6 AC 26 ms 928 KB
7 AC 25 ms 928 KB
8 AC 25 ms 932 KB
9 AC 25 ms 928 KB