Submission #853313

#	Time	Username	Problem	Language	Result	Execution time	Memory
853313		8pete8	Discharging (NOI20_discharging)	C++14	100 / 100	97 ms	30712 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;}
deque<line>con;
int val(int pos,int x){return x*con[pos].m+con[pos].c;}
void add(line a){
    while(con.size()>1&&(intersect(con[con.size()-1],a)<(intersect(con[con.size()-1],con[con.size()-2]))))con.pop_back();
    con.push_back(a);
}
int qry(int x){
    while(con.size()>1){
        if(val(0,x)>val(1,x))con.pop_front();
        else break;
    }
    return val(0,x);
}
/*
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]});
        if(i>1)dp[i]=min(dp[i],qry(v[i])+v[i]*(n+1));
    }
    cout<<dp[n]<<'\n';
}

Compilation message (stderr)

Discharging.cpp:33:13: warning: 'bool cmp(std::pair<long long int, line>, std::pair<long long int, line>)' defined but not used [-Wunused-function]
   33 | static bool cmp(pair<int,line>a,pair<int,line>b){return a.f<b.f;}
      |             ^~~

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