Submission #853308

#TimeUsernameProblemLanguageResultExecution timeMemory
8533088pete8Discharging (NOI20_discharging)C++17
0 / 100
102 ms23900 KiB
#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]; for(int i=1;i<=n;i++)p[i]=max(p[i-1],v[i]),v[i]=p[i]; add(line{0,0}); for(int i=1;i<=n;i++){ if(v[i]==v[i-1]&&i>1)dp[i]=dp[i-1]; //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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...