結果

問題 No.719 Coprime
コンテスト
ユーザー snrnsidy
提出日時 2021-07-15 15:08:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 827 bytes
コンパイル時間 2,631 ms
コンパイル使用メモリ 194,912 KB
最終ジャッジ日時 2025-01-23 01:06:24
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector <int> prime = {2,3,5,7,11,13,17,19,23,29,31};
int dp[1301][1<<11];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N;
	
	cin >> N;
	
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<(1<<11);j++)
		{
			dp[i][j] = -1e9;
		}
	}
	
	dp[1][0] = 0;
	
	for(int i=1;i<N;i++)
	{
		int bitmask = 0;
		for(int j=0;j<prime.size();j++)
		{
			if(((i+1)%prime[j])==0)
			{
				bitmask += (1<<j);
			}
		}
		//cout << i+1 << ' ' << bitmask << '\n';
		for(int j=0;j<(1<<11);j++)
		{
			if(dp[i][j]<=-1e9) continue;
			dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
			if((j&bitmask)) continue;
			dp[i+1][bitmask + j] = max(dp[i+1][bitmask + j],dp[i][j] + (i+1));
		}
	}
	
	int res = 0;
	
	for(int j=0;j<(1<<11);j++)
	{
		res = max(res,dp[N][j]);
	}
	
	cout << res << '\n';
	
	return 0;
}
0