Submission #52620548

---

Source Code Expand

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <time.h> 
using namespace std;
using namespace __gnu_pbds; 
#define ll long long
// For multiset
#define ordered_set tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
// For ordered set
// #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

long long nCR(int n, int r) {
    if(n==0){
        return 0;
    }
    if(n<r){
        return 0;
    }
    //https://stackoverflow.com/questions/11809502/which-is-better-way-to-calculate-ncr
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}
ll powerMod(ll x, ll y, ll mod){
    ll res = 1;    
    x = x % mod; 
    while (y > 0){
        if (y & 1){
            res = ((res%mod)*(x%mod)) % mod;
        }
        y = y>>1;
        x = ((x%mod)*(x%mod)) % mod;
    }
    return res;
}
ll power(ll x, ll y){
    ll res = 1;    
    while (y > 0){
        if (y & 1){
            res = ((res)*(x));
        }
        y = y>>1;
        x = ((x)*(x));
    }
    return res;
}
 // Returns n^(-1) mod p
ll modInverse(ll n, ll mod) {
    return powerMod(n, mod-2, mod);
}
vector<ll>fact(1e6+1,1);
void precomputeFactorial(ll mod){
    fact[0]=1;
    for(ll i=1;i<=1000000;++i){
        fact[i]=(i%mod)*(fact[i-1]%mod);
        fact[i]%=mod;
    }
}
// Returns nCr % p using Fermat's little theorem.
ll nCrModPFermat(ll n, ll r, ll mod) {
    if(n<r){
        return 0;
    }
    if (r==0){
        return 1;
    }
    if(fact[2]==1){
        precomputeFactorial(mod);
    }
    return (fact[n]* modInverse(fact[r], mod) % mod * modInverse(fact[n-r], mod) % mod) % mod;
}
// https://codeforces.com/blog/entry/62393 http://xorshift.di.unimi.it/splitmix64.c
struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM);}};
ll find(ll i,vector<ll>&parent){ if(parent[i]!=i){ return parent[i] = find(parent[i],parent); } return parent[i];}

void merge(ll a,ll b,vector<ll>&rank,vector<ll>&parent){
    ll x = find(a,parent);
    ll y = find(b,parent);
    if(x==y){
        return;
    }
    if(rank[x]>=rank[y]){
        parent[y]=x;
        // cout<<"rank[y] = "<<rank[]
        rank[x]+=rank[y];
        rank[y]=0;
    }
    else{
        parent[x]=y;
        rank[y]+=rank[x];
        rank[x]=0;
    }
}

vector<vector<ll>>dir={{0,-1},{0,1},{1,0},{-1,0}};
ll max(ll a,ll b){ return a>b?a:b;}
ll min(ll a,ll b){ return a<b?a:b;}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
ll complement(ll x,ll n){ return (x^(n-1));}
bool checkPrime(ll num){for(ll i=2;i<=sqrt(num);++i){if(num%i==0){return false;}}return true;}
bool isSorted(vector<ll>&vect){for(ll i=1;i<vect.size();++i){if(vect[i]<vect[i-1]){return false;}}return true;}
bool isPowerOfTwo(ll num){return (num&(num-1))==0;}
template <typename T> bool allEqual(const std::vector<T>& vec) { if (vec.empty()) { return true; } T reference = vec[0]; for (size_t i = 1; i < vec.size(); ++i) { if (vec[i] != reference) { return false; }} return true;}


const char nl = '\n';
const char sp = ' ';
void yesno(bool a) { cout << (a ? "Yes\n" : "No\n"); }
template<typename L, typename R> ostream& operator<<(ostream& out, const pair<L, R>& p) { out << '(' << p.first << ',' << p.second << ')';return out;} 
template<typename T> ostream& operator<<(ostream& out, const vector<T>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename T> ostream& operator<<(ostream& out, const set<T>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename T> ostream& operator<<(ostream& out, const unordered_set<T>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename T> ostream& operator<<(ostream& out, const unordered_set<T,custom_hash>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename K, typename V> ostream& operator<<(ostream& out, const map<K, V>& m) { out << '['; for (auto &it : m) { out << it.first << ':' << it.second << sp;}out << "]\n";return out;}
template<typename K, typename V> ostream& operator<<(ostream& out, const unordered_map<K, V>& m) { out << '['; for (auto &it : m) { out << it.first << ':' << it.second << sp; }out << "]\n";return out;}
template<typename K, typename V> ostream& operator<<(ostream& out, const unordered_map<K, V,custom_hash>& m) { out << '['; for (auto &it : m) { out << it.first << ':' << it.second << sp; }out << "]\n";return out;}
void print(vector<ll>&arr,ll index=0){ for(ll i=index;i<arr.size();++i){ cout<<arr[i]<<" ";} cout<<endl;} 

ll maxN=200009;
vector<ll>segTree(4*maxN);
vector<ll>segArr(maxN);

void build(ll node,ll start,ll end){
    if(start==end){
        segTree[node]=segArr[start];
        return;
    }
    ll mid = start+(end-start)/2;
    build(2*node,start,mid);
    build(2*node+1,mid+1,end);
    segTree[node]=segTree[2*node]+segTree[2*node+1];
}

ll query(ll node,ll start,ll end,ll l,ll r){
    if(l>end||r<start){
        return 0;
    }
    if(l<=start&&r>=end){
        return segTree[node];
    }
    ll mid = start+(end-start)/2;
    auto p1 = query(2*node,start,mid,l,r);
    auto p2 = query(2*node+1,mid+1,end,l,r);
    return p1+p2;
}

void update(ll node,ll start,ll end,ll index,ll value){
    if(start==end){
        segArr[start]=value;
        segTree[node]=value;
        return;
    }
    ll mid = start+(end-start)/2;
    if(mid>=index){
        update(2*node,start,mid,index,value);
    }
    else{
        update(2*node+1,mid+1,end,index,value);
    }
    segTree[node]=segTree[2*node]+segTree[2*node+1];
}

vector<ll> manacher_odd(string &s){
    ll n = s.length();
    s = "$"+s+"^";
    vector<ll>p(n+2);
    ll l=1,r=1;
    for(ll i=1;i<=n;++i){
        p[i]=max(0,min(r-i,p[l+(r-i)]));
        while(s[i-p[i]]==s[i+p[i]]){
            p[i]++;
        }
        if(i+p[i]>r){
            l = i-p[i];
            r = i+p[i];
        }
    }
    return {p.begin()+1,p.end()-1};
}

vector<ll> manacher(string s) {
    string str;
    for(auto &ch:s){
        str.push_back('#');
        str.push_back(ch);
    }
    str.push_back('#');
    vector<ll>arr = manacher_odd(str);
    return {arr.begin()+1,arr.end()-1};
}

bool isValid(vector<ll>&res){
    for(ll i=0;i<res.size()-1;++i){
        if(abs(res[i]-res[i+1])>1){
            return false;
        }
    }
    return true;
}

unordered_map<ll,double>dp;

double helper(ll n,ll a,ll x,double y){
    if(n==0){
        return 0;
    }
    if(dp.count(n)){
        return dp[n];
    }
    double res = LONG_LONG_MAX;
    res = x+helper(n/a,a,x,y);
    res = min(res,1.2*y+0.2*(helper(n/2,a,x,y)+helper(n/3,a,x,y)+helper(n/4,a,x,y)+helper(n/5,a,x,y)+helper(n/6,a,x,y)));
    return dp[n]=res;
}

void solve(bool printTestcase){
    ll n,a,x,y;
    cin>>n>>a>>x>>y;
    cout<<helper(n,a,x,y);
}   

int main() {
    cout.precision(9); cout.setf(ios::fixed);
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
    ll t=1;
    // cin>>t;
    for(ll i=1;i<=t;++i){
        solve(false);
    }
}

Submission Info

Compile Error

./Main.cpp:111:44: warning: comparison of integers of different signs: 'long long' and 'size_type' (aka 'unsigned long') [-Wsign-compare]
bool isSorted(vector<ll>&vect){for(ll i=1;i<vect.size();++i){if(vect[i]<vect[i-1]){return false;}}return true;}
                                          ~^~~~~~~~~~~~
./Main.cpp:127:56: warning: comparison of integers of different signs: 'long long' and 'size_type' (aka 'unsigned long') [-Wsign-compare]
void print(vector<ll>&arr,ll index=0){ for(ll i=index;i<arr.size();++i){ cout<<arr[i]<<" ";} cout<<endl;} 
                                                      ~^~~~~~~~~~~
./Main.cpp:203:17: warning: comparison of integers of different signs: 'long long' and 'size_type' (aka 'unsigned long') [-Wsign-compare]
    for(ll i=0;i<res.size()-1;++i){
               ~^~~~~~~~~~~~~
./Main.cpp:220:18: warning: implicit conversion from 'long long' to 'double' changes value from 9223372036854775807 to 9223372036854775808 [-Wimplicit-const-int-float-conversion]
    double res = LONG_LONG_MAX;
           ~~~   ^~~~~~~~~~~~~
/usr/lib/llvm-16/lib/clang/16/include/limits.h:118:24: note: expanded from macro 'LONG_LONG_MAX'
#define LONG_LONG_MAX  __LONG_LONG_MAX__
                       ^~~~~~~~~~~~~~~~~
<built-in>:106:27: note: expanded from macro '__LONG_LONG_MAX__'
#define __LONG_LONG_MAX__ 9223372036854775807LL
                          ^~~~~~~~~~~~~~~~~~~~~
./Main.cpp:226:17: warning: unused parameter 'printTestcase' [-Wunused-parameter]
void solve(bool printTestcase){
                ^
5 warnings generated.

Judge Result