Submission #224760

#	Time	Username	Problem	Language	Result	Execution time	Memory
224760		Nightlight	Feast (NOI19_feast)	C++14	100 / 100	251 ms	15036 KiB

feast

#include <bits/stdc++.h>
#define pii pair<long long, int>
#define abval first
#define pos second
#define ABS(n) (n < 0 ? -n : n)
using namespace std;

int N, K, P;
long long A[300005];
int L[300005], R[300005];
long long ans = 0;
set<pii> seto;

int main() {
//  freopen("inp", "r", stdin);
  scanf("%d %d", &N, &K);
  long long tmp;
  while(N--) {
    scanf("%lld", &tmp);
    if(P == 0) {
      if(tmp <= 0) continue;
      else {
        A[++P] = tmp;
      }
    }else if(!((A[P] > 0) ^ (tmp > 0))) {
      A[P] += tmp;
    }else {
      A[++P] = tmp;
    }
  }
  if(A[P] < 0) {
    A[P] = 0;
    P--;
  }
  for(int i = 1; i <= P; i++) {
    seto.insert({ABS(A[i]), i});
    L[i] = i - 1;
    R[i] = i + 1;
  }
  R[P] = 0;
  int cnt = (P >> 1) + 1;
  long long l, m, r, tmpval;
  while(cnt > K) {
    pii now = *seto.begin();
    seto.erase(now);
    m = now.pos, l = L[m], r = R[m];
    tmpval = A[m];
    if(A[m] > 0)cnt--;
    if(l != 0) {
      if(A[l] > 0) cnt--;
      seto.erase({ABS(A[l]), l});
      tmpval += A[l];
      if(L[l] != 0) R[L[l]] = m;
    } 
    if(r != 0) {
      if(A[r] > 0) cnt--;
      seto.erase({ABS(A[r]), r});
      tmpval += A[r];
      if(R[r] != 0) L[R[r]] = m;
    }
    A[m] = tmpval;
    A[l] = 0, A[r] = 0;
    L[m] = L[l], R[m] = R[r];
    if(L[m] == 0 && A[m] < 0) {
      L[R[m]] = 0;
      A[m] = 0;
    }else if(R[m] == 0 && A[m] < 0) {
      R[L[m]] = 0;
      A[m] = 0;
    }else seto.insert({ABS(tmpval), m});
    cnt += (A[m] > 0);
//    for(int i = 1; i <= P; i++) {
//      cout << A[i] << " ";
//    }
//    cout << "\n";
  }
  for(auto i : seto) {
    ans += A[i.pos] > 0 ? A[i.pos] : 0;
  }
  printf("%lld\n", ans);
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &K);
   ~~~~~^~~~~~~~~~~~~~~~~
feast.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &tmp);
     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29