QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#649049 | #9307. Clock Master | adivse# | TL | 0ms | 0kb | C++20 | 2.4kb | 2024-10-17 21:26:28 | 2024-10-17 21:26:29 |
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
template<typename... Args>
void bubu(Args... args) { cout << ":: "; ((cout << args << " "), ...); cout << endl; }
template<typename T>
void bubu(vector<T> tem) { for (auto x : tem) cout << x << ' '; cout << endl; }
void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
inline int max(int a, int b) { if (a < b) return b; return a; }
inline int min(int a, int b) { if (a < b) return a; return b; }
using PII = pair<int, int>;
using i128 = __int128;
//--------------------------------------------------------------------------------
const int N = 3e4 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
vector<int> prime;
bool biao[N];
double dp[3300][30010];
//--------------------------------------------------------------------------------
void dfs() {
rep(i, 2, N - 1) {
if (biao[i]) continue;
prime.push_back(i);
for (int j = i; j < N; j += i) {
biao[j] = 1;
}
}
}
signed main() {
// kuaidu();
dfs();
int len = prime.size();
// cout << len << endl;
int cnt = -1;
rep(i, 0, len - 1) {
if (prime[i] > N - 1) break;
++cnt;
// cout << prime[i] << endl;
rep(j, 0, N - 1) {
rep(k, 1, 30) {
int tem = pow(prime[i], k);
// bubu(tem);
double v = log(tem); int w = tem;
if (i == 0) {
if (j - w >= 0) dp[i][j] = max(dp[i][j], dp[i][j - w] + v);
continue;
}
if (j >= w) {
dp[i][j] = max({ dp[i][j],dp[i - 1][j], dp[i - 1][j - w] + v });
// cout << "asdsa" << endl;
}
else dp[i][j] = max({ dp[i - 1][j],dp[i][j] });
if (w > N - 1) break;
}
}
}
cin >> T;
while (T--) {
cin >> n;
cout << fixed << setprecision(10) << dp[cnt][n] << endl;
// rep(i, 1, n) cout << dp[len - 1][i] << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 7 10