Submission #1300140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300140		thdh__	Discharging (NOI20_discharging)	C++20	100 / 100	114 ms	23940 KiB

Discharging

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ii pair<int, int>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define int ll

using namespace std;

const int N = 3e5+5;
const int mod = 1e9+7;
const int inf = 1e18;

const double INF = 1/.0;
struct Line {
    int a, b;	
    mutable double p;
    bool operator<(const Line& o) const {
        if (o.a == INT_MAX && o.b == INT_MAX) return p < o.p;
        return a < o.a;
    }
};
struct CHTMax {
    multiset<Line> myLC;
    bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) {
        if (y == myLC.end()) return x->p = INF, false;
        if (x->a == y->a) x->p = (x->b > y->b) ? INF : -INF;
        else x->p = (double)(y->b - x->b) / (x->a - y->a);
        return x->p >= y->p;
    }
    void add(int a, int b) {
        auto x = myLC.insert({ a, b, 0 }), y = next(x);
        while (isect(x, y)) y = myLC.erase(y);
        if ((y = x) != myLC.begin() && isect(--y, x)) isect(y, myLC.erase(x));
        while ((x = y) != myLC.begin() && (--x)->p >= y->p)
            isect(x, myLC.erase(y)), y = x;
    }
    int query(int x) {
        Line l = *myLC.lower_bound({ INT_MAX, INT_MAX, x });
        return l.a * x + l.b;
    }
};

void solve() 
{
    int n;
	cin>>n;
	vector<int> t(n), pref(n), dp(n);
	for (int i = 0; i < n; i++) cin>>t[i];
	pref[0] = t[0];
	for (int i = 1; i < n; i++) pref[i] = max(t[i], pref[i-1]);
	CHTMax cht;
	cht.add(-n, 0);
	for (int i = 0; i < n; i++) 
	{
		dp[i] = -cht.query(pref[i]);
		cht.add(-(n-1-i), (-dp[i]));
	}
	cout<<dp[n-1];
}

signed main() 
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    solve();
}

Compilation message (stderr)

Discharging.cpp: In member function 'long long int CHTMax::query(long long int)':
Discharging.cpp:41:56: warning: narrowing conversion of 'x' from 'long long int' to 'double' [-Wnarrowing]
   41 |         Line l = *myLC.lower_bound({ INT_MAX, INT_MAX, x });
      |                                                        ^

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