Submission #853310

#	Time	Username	Problem	Language	Result	Execution time	Memory
853310		8pete8	Discharging (NOI20_discharging)	C++14	58 / 100	105 ms	30584 KiB

Discharging

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
struct line{int m,c;};
double intersect(line a,line b){return ((b.c-a.c)*1.0/(a.m-b.m)*1.0);}
static bool cmp(pair<int,line>a,pair<int,line>b){return a.f<b.f;}
vector<pair<int,line>>con;
void add(line a){
    while(con.size()>1&&(intersect(con.back().s,a)<=(intersect(con[con.size()-1].s,con[con.size()-2].s))))con.pop_back();
    if(con.empty())con.pb({0,a});
    else con.pb({intersect(con.back().s,a),a});
}
int qry(int x){
    auto it=ub(all(con),make_pair(x,line{}),cmp);
    it--;
    line tmp=(*it).s;
    return x*(tmp.m)+tmp.c;
}
/*
dpi =dp(j)+ti*(n-j+1)
*/
int32_t main(){
    fastio
    int n;cin>>n;
    vector<int>v(n+1),p(n+1),dp(n+1,INT_MAX);
    dp[0]=0;
    for(int i=1;i<=n;i++)cin>>v[i],v[i]=max(v[i-1],v[i]);
    add(line{0,0});
    for(int i=1;i<=n;i++){
        dp[i]=v[i]*n;
        //ti(1-j)+dp(j-1)
        //-tij+dp(j-1)+ti
        add(line{-i,dp[i-1]});
        dp[i]=min(dp[i],qry(v[i])+v[i]*(n+1));
    }
    cout<<dp[n]<<'\n';
}

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