제출 #853313

#제출 시각아이디문제언어결과실행 시간메모리
8533138pete8Discharging (NOI20_discharging)C++14
100 / 100
97 ms30712 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;} 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'; }

컴파일 시 표준 에러 (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;}
      |             ^~~
#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...