Submission #996354

#	Time	Username	Problem	Language	Result	Execution time	Memory
996354		PCTprobability	Meetings (IOI18_meetings)	C++17	19 / 100	5516 ms	7060 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class A,class B>
bool chmin(A &a,B b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
ll solve(vector<ll> a){
  ll n=a.size();
  vector<ll> l(n),r(n);
  ll ans=(1ll<<60);
  {
    ll sum=0;
    vector<pair<ll,ll>> st;
    for(int i=0;i<n;i++){
      ll x=a[i],y=1;
      while(st.size()&&st.back().first<=x){
        sum-=st.back().first*st.back().second;
        y+=st.back().second;
        st.pop_back();
      }
      st.push_back({x,y});
      sum+=x*y;
      l[i]=sum;
    }
  }
  {
    ll sum=0;
    vector<pair<ll,ll>> st;
    for(int i=n-1;i>=0;i--){
      ll x=a[i],y=1;
      while(st.size()&&st.back().first<=x){
        sum-=st.back().first*st.back().second;
        y+=st.back().second;
        st.pop_back();
      }
      st.push_back({x,y});
      sum+=x*y;
      r[i]=sum;
    }
  }
  for(int i=0;i<n;i++) chmin(ans,l[i]+r[i]-a[i]);
  return ans;
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,std::vector<int> r) {
  int n=h.size();
  int q=l.size();
  vector<ll> ans(q,1ll<<60);
  for(int i=0;i<q;i++){
    vector<ll> b;
    for(int j=l[i];j<=r[i];j++) b.push_back(h[j]);
    ans[i]=solve(b);
  }
  return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:51:7: warning: unused variable 'n' [-Wunused-variable]
   51 |   int n=h.size();
      |       ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40