QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#649049#9307. Clock Masteradivse#TL 0ms0kbC++202.4kb2024-10-17 21:26:282024-10-17 21:26:29

Judging History

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

  • [2024-10-17 21:26:29]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-17 21:26:28]
  • 提交

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

output:


result: