QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693402#9307. Clock Masterqinglu09ML 0ms0kbC++231.9kb2024-10-31 16:05:092024-10-31 16:05:10

Judging History

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

  • [2024-10-31 16:05:10]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-31 16:05:09]
  • 提交

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

double dp[N + 1][3247], 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)
        {
            dp[i][j] = max(dp[i][j], dp[i + 1][j]);
            if(j) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            ll cur = d[j];
            while(1)
            {
                if(cur > i) break;
                // if(i - cur == 29991 && cur == 5) debug(dp[i][j]);
                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) << dp[30000 - x][siz - 1] << 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);
    }
    dfs();
    cin>>T;
    while(T--)
    {
        solve();
    }
    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.693147181
2.484906650
3.401197382

result: