QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692506#9307. Clock Masterqinglu09#TL 0ms0kbC++231.9kb2024-10-31 14:38:132024-10-31 14:38:37

Judging History

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

  • [2024-10-31 14:38:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-31 14:38:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> PLL;
#define endl '\n'
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const ll N = 30001;
#define debug(x) cout<<#x<<": "<<x<<endl

long double dp[N][3246], ans[N], lg[N];
ll siz;

bool vis[N];
int prime[N];//0是质数
vector<int>d;
void init_prime()
{
    vis[1] = 1;
    for(int i = 2; i < N; i++)
    {
        if(!vis[i])
        {
            prime[++prime[0]] = i;
            d.push_back(i);
        }
        for(int j = 1; i * prime[j] < N; j++)
        {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

void dfs()
{
    per(i, N - 1, 0)
    {
        rep(j, 0, siz - 1)
        {
            ll cur = d[j];
            while(1)
            {
                if(cur > i) break;
                dp[i - cur][j + 1] = max(dp[i - cur][j + 1], dp[i][j] + lg[cur]);
                cur *= d[j];
            }
        }
    }
}



void solve()
{
    ll x;
    cin >> x;
    cout << fixed << setprecision(9) << ans[x] << endl;
    // rep(i, 1, N - 1)
    // {
    //     cout << "," <<  fixed << setprecision(9) << ans[i];
    // }
}

int main()
{

    #ifndef ONLINE_JUDGE
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll T=1;
    init_prime();
    siz = d.size();
    lg[0] = 0;
    rep(i, 1, N - 1)
    {
        lg[i] = log(i);
    }
    // cout << siz << endl;;
    dfs();
    rep(i, 1, N - 1)
    {
        rep(j, 0, siz - 1)
        {
            ans[i] = max(ans[i], dp[N - 1- i][j]);
        }
    }
    cin>>T;
    while(T--)
    {
        solve();
    }
    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: