結果

問題 No.1515 Making Many Multiples
ユーザー kotatsugame
提出日時 2021-05-21 21:50:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 720 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 68,748 KB
実行使用メモリ 19,232 KB
最終ジャッジ日時 2024-10-10 08:21:52
合計ジャッジ時間 3,575 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#include<algorithm>
using namespace std;
int N,K,X,Y;
int dp[2000][2000];
int mH[2000],mW[2000];
main()
{
	cin>>N>>K>>X>>Y;
	X%=K;
	Y%=K;
	for(int i=0;i<K;i++)for(int j=0;j<K;j++)dp[i][j]=-1e9;
	for(int i=0;i<K;i++)mH[i]=mW[i]=-1e9;
	dp[X][Y]=0;
	mH[X]=0;
	mW[Y]=0;
	for(int i=0;i<N;i++)
	{
		int A;cin>>A;A%=K;
		for(int h=0;h<K;h++)
		{
			int w=(K+K-A-h)%K;
			dp[h][w]++;
			mH[h]=max(mH[h],dp[h][w]);
			mW[w]=max(mW[w],dp[h][w]);
		}
		for(int h=0;h<K;h++)dp[h][A]=mH[h];
		for(int w=0;w<K;w++)dp[A][w]=mW[w];
		for(int h=0;h<K;h++)mW[A]=max(mW[A],dp[h][A]);
		for(int w=0;w<K;w++)mH[A]=max(mH[A],dp[A][w]);
	}
	int ans=0;
	for(int i=0;i<K;i++)ans=max(ans,max(mH[i],mW[i]));
	cout<<ans<<endl;
}
0