제출 #1193438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193438		loom	Discharging (NOI20_discharging)	C++20	100 / 100	75 ms	8260 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define nl '\n'

ld xisn(pair<int,int> l1, pair<int,int> l2){
   auto [m1, c1] = l1;
   auto [m2, c2] = l2;

   return (ld)(c2 - c1)/(m1 - m2);
}

int yval(pair<int,int> l, int x){
   auto [m, c] = l;
   return m*x + c;
}

inline void solve(){
   int n;
   cin>>n;
   int a[n];
   for(int i=0; i<n; i++) cin>>a[i];

   deque<pair<int,int>> dq;
   int ldp = 0, mx = 0;
   for(int i=0; i<n; i++){
      mx = max(mx, a[i]);
      pair<int,int> cur = {i, ldp};

      while(dq.size() >= 2 and xisn(dq.back(), cur) <= xisn(dq.back(), dq[(int)dq.size()-2])) dq.pop_back();
      dq.push_back(cur);

      while(dq.size() >= 2 and yval(dq[0], mx) <= yval(dq[1], mx)) dq.pop_front();
      ldp = yval(dq[0], mx) - n*mx;
   }

   cout<<-ldp;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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