Submission #1284996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284996		diep38	Discharging (NOI20_discharging)	C++20	100 / 100	109 ms	16088 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define ed "\n"
#define fi first
#define se second
#define irs insert
#define pb push_back
#define pi pair<int,int>
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x>>i)&1)
#define ON(x, i) ((x)  MASK(i))
#define OFF(x, i) ((x) & ~MASK(i))
#define ALL(v) v.begin() , v.end()
#define pii pair<int,pair<int,int>>
#define fl(i,a,b) for(int i=a;i>=b;--i)
#define fis(i,a,b) for(int i=a;i<=b;++i)
#define i128 __int128
const int mod=1e9+7;
const int Mdem=998244353;
const int LOG=19;
const int base=31;
const int maxn=1e6+5;
const int bl = 320;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}

template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
template <class T>
void compress(vector <T> &v) {
    sort(ALL(v));
    v.erase(unique(ALL(v)), (v).end());
}

void add(int &a, int b) {   a += b; if (a >= mod)   a -= mod;   }
void sub(int &a, int b) {   a -= b; if (a <  0)     a += mod;   }
struct line{
    int a, b;
    line(int _a, int _b){
        a = _a; b = _b;
    }
    int Fval(int x){ return a * x + b;}
};

int n, c, a[maxn], f[maxn];
//vector<line> hull;

struct Convex_Hull_Trick{
    vector<line> hull;
    Convex_Hull_Trick(){ hull.clear();}
    bool ccw(line A, line B, line C){
        i128 y = (i128)(A.a - B.a) * (C.b - A.b);
        i128 x = (i128)(B.b - A.b) * (A.a - C.a);
        return x >= y;
        return 1.0 * (B.a - A.a) / (C.a - A.a) >= 1.0 * (B.b - A.b) / (C.b - A.b);
    }
    void add(line x){
        while(hull.size() >= 2 && ccw(hull[(int)hull.size() -2], hull.back(), x)) hull.pop_back();
        hull.pb(x);
    }
    int get(int x){
        int ans = 1e18;
        int l = 0, r = (int)hull.size() - 1;
        while(l <= r){
            int mid = l + r >> 1;
            int val = hull[mid].Fval(x);
            minimize(ans, val);
            if(mid > 0 && hull[mid - 1].Fval(x) < val) r = mid - 1;
            else if(mid < (int)hull.size() - 1 && hull[mid + 1].Fval(x) < val) l = mid + 1;
            else break;
        }
        return ans;
    }
};
signed main(){
    fast;
    cin >> n;
    fis(i, 1, n) f[i] = 6e18;
    fis(i, 1, n) cin >> a[i];
    fis(i, 1, n) a[i] = max(a[i], a[i - 1]);
    Convex_Hull_Trick L = Convex_Hull_Trick();
    L.add({0, 0});
    fis(i, 1, n){
        f[i] = L.get(a[i]) + a[i] * n;
        L.add({-i, f[i]});
    }
    cout << f[n];



    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28