結果
問題 | No.732 3PrimeCounting |
ユーザー |
|
提出日時 | 2021-06-28 09:32:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 851 bytes |
コンパイル時間 | 1,907 ms |
コンパイル使用メモリ | 195,628 KB |
最終ジャッジ日時 | 2025-01-22 14:46:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 87 TLE * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector <long long int> prime; void eratos() { bool isprime[300005]; memset(isprime, true, sizeof(isprime)); for (int i = 2; i <= 300000; i++) { if (isprime[i]) { prime.push_back(i); for (int j = 2 * i; j <= 300000; j += i) { isprime[j] = false; } } } } long long int dp[4][300005]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; long long int res = 0; cin >> n; eratos(); for (int i = 0; i < prime.size(); i++) { if (prime[i] > n) break; for (int j = 2; j >= 1; j--) { for (int k = 2; k <= 3 * prime[i]; k++) { if (prime[i] + k > 3 * n) break; dp[j + 1][prime[i] + k] += dp[j][k]; } } dp[1][prime[i]] = 1; } for (int i = 0; i < prime.size(); i++) { res += dp[3][prime[i]]; } cout << res << '\n'; return 0; }