Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <cstdio>
using namespace std;

int n,m,last,s[100100],a[100100],b[100100];
double start[100100];

void addLine(int A,int B)
{
    double x=-1e18;

    while (last>1)
    {
        x=1.0*(B-b[last])/(a[last]-A);
        if (x>start[last]) break;
        last--;
    }

    if (last) x=1.0*(B-b[last])/(a[last]-A);
    a[++last]=A; b[last]=B; start[last]=x;
}

long long findHighest(int f,int F)
{
    double x=1.0*f/F;
    int low=1,high=last,best=1;

    while (low<=high)
    {
        int mid=(low+high)>>1;
        if (start[mid]>x) high=mid-1;
        else best=mid, low=mid+1;
    }

    return 1LL*f*a[best]+1LL*F*b[best];
}

int main()
{
    int f,F,x;
    long long t=0;

    cin >> n >> m;
    for (int i=1;i<=n;i++) scanf("%d",&x), s[i]=s[i-1]+x, addLine(s[i],-s[i-1]);

    cin >> F;
    while (--m) f=F, scanf("%d",&F), t+=findHighest(f,F);

    cout << t+1LL*F*s[n] << endl;
}

Code mẫu của RR

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
using namespace std;

const int MN = 100111;

int nWorker, nCar;
long long t[MN], f[MN];

struct Line {
    long long a, b;

    long long get(long long f1, long long f2) {
        return a * f1 + b * f2;
    }
} a[MN], ch[MN];

bool operator < (const Line &x, const Line &y) {
    if (x.a != y.a) return x.a < y.a;
    return x.b < y.b;
}

int nLines;

bool bad(Line x, Line y, Line z) {
    return (z.b-x.b) * (y.a-x.a) >= (x.b-y.b) * (x.a-z.a);
}

int main() {
    ios :: sync_with_stdio(false);
    while (cin >> nWorker >> nCar) {
        FOR(i,1,nWorker) {
            cin >> t[i];
            t[i] += t[i-1];
        }
        FOR(i,1,nCar) cin >> f[i];

        FOR(i,1,nWorker) {
            a[i].a = t[i];
            a[i].b = -t[i-1];
        }

        sort(a+1, a+nWorker+1);

        nLines = 2; ch[1] = a[1]; ch[2] = a[2];
        FOR(i,3,nWorker) {
            while (nLines >= 2 && bad(ch[nLines-1], ch[nLines], a[i])) --nLines;
            ch[++nLines] = a[i];
        }

        // FOR(i,1,nLines) cout << a[i].a << ' ' << a[i].b << endl;

        long long res = 0;
        FOR(i,1,nWorker) {
            res += (t[i]-t[i-1]) * f[nCar];
        }
        FOR(i,2,nCar) {
            long long now = 0;
            int l = 1, r = nLines;
            while (l <= r) {
                int x1 = (l + l + r) / 3, x2 = (l + r + r) / 3;
                long long y1 = ch[x1].get(f[i-1], f[i]);
                long long y2 = ch[x2].get(f[i-1], f[i]);

                now = max(now, max(y1, y2));
                if (y1 > y2) r = x2 - 1;
                else l = x1 + 1;
            }
            res += now;
        }
        cout << res << endl;
    }
    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define maxn 100005
using namespace std;

int n,m;
int comp[maxn],fact[maxn];
pair<long long,long long> pts[maxn];
vector< pair<long long,long long> > hull;

long long crossProduct(pair<long long,long long> A,pair<long long,long long> B,pair<long long,long long> C) {
    long long xa = B.first - A.first,ya = B.second - A.second;
    long long xb = C.first - B.first,yb = C.second - B.second;
    return (xa * yb - xb * ya);
}

int main() {
    //freopen("traka.in.2","r",stdin);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &comp[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &fact[i]);

    pts[1] = make_pair(comp[1],0);
    for (int i = 2; i <= n; i++) pts[i] = make_pair(pts[i - 1].first + comp[i],pts[i - 1].second - comp[i - 1]);
    for (int i = n; i; i--) {
        while (hull.size() > 1 && crossProduct(hull[hull.size() - 2],hull[hull.size() - 1],pts[i]) <= 0) hull.pop_back();
        hull.push_back(pts[i]);
    }
    long long prev = 0;
    for (int i = 2; i <= m; i++) {
        long long maxDelta = 0;
        int low = 0,high = hull.size() - 1;
        while (high - low > 3) {
            int m1 = (low + low + high)/3,m2 = (low + high + high)/3;
            long long T1 = hull[m1].first * fact[i - 1] + hull[m1].second * fact[i];
            long long T2 = hull[m2].first * fact[i - 1] + hull[m2].second * fact[i];
            if (T1 > T2) {
                maxDelta = max(maxDelta,T1);
                high = m2 - 1;
            }
            else {
                maxDelta = max(maxDelta,T2);
                low = m1 + 1;
            }
        }
        for (int j = low; j <= high; j++) maxDelta = max(maxDelta,1LL * hull[j].first * fact[i - 1] + 1LL * hull[j].second * fact[i]);
        prev += maxDelta;
    }
    for (int j = 1; j <= n; j++) prev += 1LL * comp[j] * fact[m];
    cout << prev << endl;
}