Submission #1092336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092336		pudelos	Tortoise (CEOI21_tortoise)	C++17	8 / 100	1 ms	452 KiB

tortoise

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define pi pair<int, int>
#define f first
#define s second
#define V vector
const int inf=1e9;
int wyn=0, licznik=0, suma_czasow=0, n;
priority_queue<pi> pq;
void wrzuc(int czas, int ile) {
  if(ile<=0) return;
  suma_czasow+=czas*ile;
  licznik+=ile;
  pq.push({czas, ile});
}
void wywal(int fosy) {
  auto [czas, ile] = pq.top();
  suma_czasow-=czas*ile;
  licznik-=ile;
  pq.pop();
  if(suma_czasow>=fosy) return;
  int ilen = (fosy-suma_czasow)/czas;
  wrzuc(czas, ilen);
}
signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n;
  V<int> A(n+1), lewo(n+1), prawo(n+1), niezerowy(n+1); 
  FOR(i, 1, n) cin >> A[i];
  int sum=0;
  int idxl=-inf, idxp=inf, idxn=inf;
  FOR(i, 1, n) {
    if(A[i]>0) sum+=A[i];
    lewo[i]=idxl;
    if(A[i]==-1) idxl=i;
  }
  for(int i=n; i>=1; --i) {
    prawo[i]=idxp;
    niezerowy[i]=idxn;
    if(A[i]==-1) idxp=i;
    if(A[i]>0) idxn=i;
  }
  FOR(i, 1, n) {
    if(A[i]<=0) continue;
    int spacer = inf;
    if(niezerowy[i]<=n && prawo[i]<=n) spacer=max(0ll, prawo[i]-niezerowy[i]);
    wrzuc(2*min(prawo[i]-i, i-lewo[i]), A[i]-1);
    wrzuc(2*min({spacer, prawo[i]-i, i-lewo[i]}), 1);
    int fosy=i+2*min({spacer, prawo[i]-i, i-lewo[i]});
    while(suma_czasow>fosy) wywal(fosy);
    wyn=max(wyn, licznik);
  }
  cout << sum-wyn << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27