QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#649052#9307. Clock Masteradivse#ML 0ms0kbC++202.4kb2024-10-17 21:27:332024-10-17 21:27:34

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 21:27:34]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-17 21:27:33]
  • 提交

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) {
            for (int k = prime[i]; k < N; k *= prime[i]) {
                int tem = k;
                double v = log(tem * 1.0); 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
Memory Limit Exceeded

input:

3
2
7
10

output:

0.6931471806
2.4849066498
3.4657359028

result: