[Codeforces] D. Devu and his Brother

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Devu and his Brother
                    Codeforces Round #251 (Div. 2)
Source            : Codeforces
Category          : Search
Algorithm         : Ternary Search
Verdict           : Accepted 

#include <bits/stdc++.h>  
   
using namespace std;  
   
static const int MAXN = 1e5 + 5;  
   
int n, m;  
long long A[MAXN], B[MAXN];  
long long SA[MAXN], SB[MAXN];  
   
long long f(long long num)  
{  
    int nn = lower_bound(A+1, A+n+1, num) - A;  
    long long changeA = num*(nn-1) - SA[nn-1];  
    int mm = lower_bound(B+1, B+m+1, num+1) - B;  
    long long changeB = 0;  
    if (mm <= m) changeB = SB[m] - SB[mm-1] - num*(m-mm+1);  
    return changeA + changeB;  
}  
   
long long ternary()  
{  
    long long low = 1;  
    long long high = 1e9;  
    while (true)  
    {  
        if (high - low < 3)  
        {  
            long long f1 = f(low);  
            long long f2 = f(low+1);  
            long long f3 = f(high);  
            return min(f1, min(f2, f3));  
        }  
        long long midA = low + (high - low)/3;  
        long long midB = high - (high - low)/3;  
        if (f(midA) <= f(midB)) high = midB;  
        else low = midA;  
    }  
}  
   
int main()  
{  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) cin >> A[i];  
    sort(A+1, A+n+1);  
    for (int i = 1; i <= n; i++) SA[i] = SA[i-1] + A[i];  
    for (int i = 1; i <= m; i++) cin >> B[i];  
    sort(B+1, B+m+1);  
    for (int i = 1; i <= m; i++) SB[i] = SB[i-1] + B[i];  
    cout << ternary();  
}  

[UVa] 13010 - Galactic taxes

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13010 - Galactic taxes
Source            : UVa Online Judge
Category          : Graph Theory, Search
Algorithm         : spfa, Ternary Search
Verdict           : Accepted  

#include <bits/stdc++.h>  
   
using namespace std;  
   
#define inf             1e13  
   
static const int maxn = 1000 + 5;  
   
struct node  
{  
    int v, A, B;  
    node() {}  
    node(int v, int A, int B)  
    {  
        this->v = v;  
        this->A = A;  
        this->B = B;  
    }  
};  
   
vector <node> g[maxn];  
   
int N, M;  
double dist[maxn];  
bool inQueue[maxn];  
   
double SPFA(double t)  
{  
    for (int i = 1; i < maxn; i++)  
    {  
        dist[i] = inf;  
        inQueue[i] = 0;  
    }  
    queue <int> PQ;  
    PQ.push(1);  
    dist[1] = 0.0;  
    inQueue[1] = 1;  
    while (!PQ.empty())  
    {  
        int u = PQ.front(); PQ.pop();  
        inQueue[u] = 0;  
        for (auto &it : g[u])  
        {  
            double cost = (double)it.A * t + (double)it.B;  
            int v = it.v;  
            if (dist[v] > dist[u] + cost)  
            {  
                dist[v] = dist[u] + cost;  
                if (!inQueue[v])  
                {  
                    inQueue[v] = 1;  
                    PQ.push(v);  
                }  
            }  
        }  
    }  
    return dist[N];  
}  
   
void ternary_search()  
{  
    double low = 0.0;  
    double high = 1440.0;  
    double ans = -inf;  
    for (int tol = 0; tol < 300; tol++)  
    {  
        double mid1 = low + (high - low) / 3.0;  
        double mid2 = high - (high - low) / 3.0;  
        double fmid1 = SPFA(mid1);  
        double fmid2 = SPFA(mid2);  
        ans = max(ans, max(fmid1, fmid2));  
        if (fmid1 < fmid2) low = mid1;  
        else high = mid2;  
    }  
    cout << fixed << setprecision(5) << ans << endl;  
}  
   
int main()  
{  
    //freopen("in.txt", "r", stdin);  
   
    while (cin >> N >> M)  
    {  
        for (int i = 0; i < M; i++)  
        {  
            int u, v, A, B;  
            cin >> u >> v >> A >> B;  
            g[u].push_back({v, A, B});  
            g[v].push_back({u, A, B});  
        }  
        ternary_search();  
        for (int i = 0; i < maxn; i++) g[i].clear();  
    }  
}