Submission #1170065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170065		altern23	Discharging (NOI20_discharging)	C++20	100 / 100	78 ms	16108 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll MAXN = 2e5;
const ll INF = 4e18;
const ll MOD = 998244353;

struct line{
    ll m, c;
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll N; cin >> N;
        vector<ll> a(N + 5), dp(N + 5);
        for(int i = 1; i <= N; i++) cin >> a[i];

        vector<line> stk;
        
        dp[0] = 0;
        stk.push_back({N, 0});

        auto intersection = [&](line A, line B){
            return (ld)(B.c - A.c) / (ld)(A.m - B.m);
        };

        auto cek = [&](line A, line B, line C){
            ll i = B.c - A.c, j = A.m - B.m;
            ll k = C.c - B.c, l = B.m - C.m;
            if(i / j != k / l) return i / j > k / l;
            i %= j, k %= l;
            return i * l > j * k;
        };

        auto ins = [&](line a){
            while(stk.size() >= 1 && stk.back().m == a.m) stk.pop_back();
            while(stk.size() >= 2){
                if(!cek(a, stk[stk.size() - 1], stk[stk.size() - 2])){
                    stk.pop_back();
                }
                else break;
            }
            stk.push_back(a);
        };

        auto F = [&](ll idx, ll x){
            return stk[idx].m * x + stk[idx].c;
        };

        ll MX = -1;
        for(int i = 1; i <= N; i++){
            MX = max(MX, a[i]);
            ll lf = 1, rg = stk.size() - 1, ans = 0;
            for(;lf <= rg;){
                ll mid = (lf + rg) / 2;
                if(intersection(stk[mid - 1], stk[mid]) <= MX){
                    ans = mid;
                    lf = mid + 1;
                }
                else rg = mid - 1;
            }
            dp[i] = F(ans, MX);
            ins({N - i, dp[i]});
        }

        cout << dp[N] << "\n";
    }   
}

/*
dp[i] = max(dp[i], dp[j] + (n - j) * MX)
*/

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