結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2016-12-09 10:32:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,100 bytes |
コンパイル時間 | 1,297 ms |
コンパイル使用メモリ | 169,676 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 05:44:28 |
合計ジャッジ時間 | 2,450 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; int N; void init(){ cin >> N; } vi pt; vi dp; void preprocess(){ vi np( N + 1 ); for( int i = 2; i < np.size(); ++i ) if( not np[ i ] ){ pt.emplace_back( i ); for( int j = i + i; j < np.size(); j += i ) np[ j ] = 1; } dp = vi( N + 1, -INF ); dp[ 0 ] = 0; for( int i = 0; i < pt.size(); ++i ) for( int j = dp.size() - 1; j >= pt[ i ]; --j ) upmax( dp[ j ], dp[ j - pt[ i ] ] + 1 ); } void solve(){ if( dp[ N ] < 0 ) dp[ N ] = -1; cout << dp[ N ] << endl; } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }