結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector <int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
int dp[2][1<<20];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N;
	
	cin >> N;
	
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<(1<<20);j++)
		{
			dp[i][j] = -1e9;
		}
	}
	
	dp[1][0] = 0;
	
	for(int i=1;i<N;i++)
	{
		memcpy(dp[0],dp[1],sizeof(dp[1]));
		fill(dp[1],dp[1]+(1<<20),-1e9);
		int bitmask = 0;
		for(int j=0;j<20;j++)
		{
			if(((i+1)%prime[j])==0)
			{
				bitmask += (1<<j);
			}
		}
		//cout << i+1 << ' ' << bitmask << '\n';
		for(int j=0;j<(1<<20);j++)
		{
			if(dp[0][j]<=-1e9) continue;
			dp[1][j] = max(dp[1][j],dp[0][j]);
			if((j&bitmask)) continue;
			dp[1][bitmask + j] = max(dp[1][bitmask + j],dp[0][j] + (i+1));
		}
	}
	
	int res = 0;
	
	for(int j=0;j<(1<<20);j++)
	{
		res = max(res,dp[1][j]);
	}
	
	cout << res << '\n';
	
	return 0;
}
0