結果

問題 No.3368 トッピング
コンテスト
ユーザー kotatsugame
提出日時 2025-11-17 21:18:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,512 ms / 2,000 ms
コード長 1,187 bytes
コンパイル時間 702 ms
コンパイル使用メモリ 72,552 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-17 21:18:31
合計ジャッジ時間 10,286 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<bitset>
#include<cassert>
using namespace std;
int N,M,C,X;
int A[2000][200];
bitset<2001>dp[3][400];
bitset<2001>R[200];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>M>>C>>X;
	for(int i=0;i<N;i++)for(int j=0;j<M;j++)cin>>A[i][j];
	long l=-1e9,r=(int)1e9+1;
	while(r-l>1)
	{
		long m=(l+r)/2;
		for(int i=0;i<3;i++)for(int j=0;j<M+M;j++)dp[i][j].reset();
		{//first
			for(int j=0;j<M;j++)
			{
				if(A[0][j]>=m)dp[1][j+j].set(0);
				if(A[0][j]>=m+C&&A[1][j]>=m+C)dp[2][j+j+1].set(2);
			}
		}
		for(int i=1;i<N;i++)
		{
			const int id=i%3;
			const int nid=(i+1)%3;
			const int nnid=(i+2)%3;
			R[M-1].reset();
			for(int j=M-2;j>=0;j--)R[j]=R[j+1]|dp[id][j+j+2]|dp[id][j+j+3];
			bitset<2001>L;
			L.reset();
			for(int j=0;j<M;j++)
			{
				if(A[i][j]>=m+C)dp[nid][j+j+1]|=dp[id][j+j+1]<<1;
				if(A[i][j]>=m)dp[nid][j+j]|=L|R[j];
				if(i+1<N&&A[i][j]>=m+C&&A[i+1][j]>=m+C)dp[nnid][j+j+1]|=(L|R[j])<<2;
				L|=dp[id][j+j]|dp[id][j+j+1];
			}
			for(int j=0;j<M+M;j++)dp[id][j].reset();
		}
		int now=N%3;
		bool fn=false;
		for(int j=0;j<M+M;j++)if((dp[now][j]>>X).any())fn=true;
		if(fn)l=m;
		else r=m;
	}
	cout<<l<<endl;
}
0