結果

問題 No.3293 Golden Cross
コンテスト
ユーザー kotatsugame
提出日時 2025-10-03 23:02:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 591 ms / 2,000 ms
コード長 1,312 bytes
コンパイル時間 607 ms
コンパイル使用メモリ 64,788 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-03 23:02:46
合計ジャッジ時間 16,533 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cassert>
using namespace std;
int H,W,K;
int A[600][600],B[600][600];
long solve(int up,long c2,long c1,long c0)
{
	assert(c2<0);
	long mx=-c1/(2*c2);
	long l=mx-20,r=mx+20;
	long ret=0;
	if(r<0)r=0;
	if(l>up)l=up;
	for(int x=max(0L,l);x<=min((long)up,r);x++)ret=max(ret,c2*x*x+c1*x+c0);
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>H>>W>>K;
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)cin>>A[i][j];
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)cin>>B[i][j];
	long S=0;
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)
	{
		long X=0,Y=0;
		int a=31,b=31,c=B[i][j];
		for(int k=0;k<W;k++)
		{
			X+=A[i][k];
			if(k!=j)a=min(a,B[i][k]);
		}
		for(int k=0;k<H;k++)
		{
			Y+=A[k][j];
			if(k!=i)b=min(b,B[k][j]);
		}
		if(a>b)swap(a,b),swap(X,Y);
		if(c<=a)
		{//only c
			int t=K>>c;
			X+=t;
			Y+=t;
			S=max(S,X*Y);
		}
		else if(c<=b)
		{//only a and c
			int up=K>>c;
			//0<=C<=up, (X+(K>>a)-C*((1<<c-a)-1))(Y+C)
			long c2=-((1<<c-a)-1);
			long c1=X+(K>>a)-Y*((1<<c-a)-1);
			long c0=(X+(K>>a))*Y;
			S=max(S,solve(up,c2,c1,c0));
		}
		else
		{//only a and b
			int up=K>>b;
			//0<=B<=up, (X+(K>>a)-B*(1<<b-a))(Y+B)
			long b2=-(1<<b-a);
			long b1=X+(K>>a)-Y*(1<<b-a);
			long b0=(X+(K>>a))*Y;
			S=max(S,solve(up,b2,b1,b0));
		}
	}
	cout<<S<<endl;
}
0