Submission #69763

#	Time	Username	Problem	Language	Result	Execution time	Memory
69763		octopuses	Homecoming (BOI18_homecoming)	C++17	0 / 100	36 ms	8876 KiB

homecoming

//Giorgi Kldiashvili

#include "homecoming.h"
#include <bits/stdc++.h>

#define ll long long


using namespace std;

const int N = 5020;

int n;
ll C[N], D[N], T[N], A[N], B[N], a[N];
int S[N];
ll answer, tot;
deque < int > d;

inline ll F(int x, int y)
{
  if(x <= y)
    return C[y - 1] - C[x - 1] + D[y];
  return C[y - 1] + C[n] - C[x - 1] + D[y];
}

ll solve(int NN, int k, int AA[], int BB[])
{
  for(int i = 0; i < N; ++ i)
    C[i] = D[i] = a[i] = S[i] = A[i] = B[i] = 0;
  answer = tot = 0;
  while(d.size()) d.pop_front();
  n = NN;
  for(int i = n; i >= 1; -- i)
  {
    A[i] = AA[i - 1];
    B[i] = BB[i - 1];
    C[i] = A[i] - B[i];
  }
  A[0] = B[0] = 0;
  for(int i = 1; i <= n; ++ i) C[i] += C[i - 1];
  answer = C[n];
  for(int i = 1; i < k; ++ i) D[n] -= B[i];
  D[n] += A[n] - B[n];
  int r = k - 1;
  if(r == 0) r = n;
  if(n == k)
    return answer;
  for(int i = n - 1; i >= 1; -- i)
  {
    D[i] = D[i + 1];
    D[i] += B[r] - A[i + 1];
    D[i] += A[i] - B[i];
    if(r <= 1)
      r = n;
    else
      r --;
  }
  for(int i = n - k; i >= 1; -- i)
  {
    while(d.size() && F(1, i) >= F(1, d.front()))
      d.pop_front();
    d.push_front(i);
  }
  S[1] = d.back();
  answer = max(answer, F(1, S[1]));
  r = n - k;
  for(int i = n; i > 1; -- i)
  {
    if(d.size() && d.back() == r)
      d.pop_back();
    if(r == 1)
      r = n;
    else
      r --;
    while(d.size() && F(i, i) >= F(i, d.front()))
      d.pop_front();
    d.push_front(i);
    S[i] = d.back();
    a[i] = F(i, S[i]);
    S[i] += k;
    if(S[i] > n) S[i] -= n;
    answer = max(answer, a[i]);
  }
  for(int i = 1; i <= n; ++ i)
  {
    for(int j = 1; j <= n; ++ j)
      T[j] = 0;
    int tt = n;
    int now = i;
    int pre = i + 1; if(pre == n + 1) pre = 1;
    while(tt --)
    {
      T[now] = T[pre];
      if((S[now] < now && S[now] <= i) || (i <= S[now] && S[now] > now))
        T[now] = max(T[now], a[now] + T[S[now]]);
      answer = max(answer, T[now]);
      pre = now;
      now --; if(now == 0) now = n;
    }
  }
  return answer;
}
/*
1
5 1
5 5 5 5 5
0 0 0 0 0
1
10 4
1 1 1 1 1 1 1 1 1 1
100000 0 0 0 0 100000 0 0 0 0
1
3 2
40 80 100
140 0 20
*/

Compilation message (stderr)

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:23:17: warning: array subscript is below array bounds [-Warray-bounds]
   return C[y - 1] + C[n] - C[x - 1] + D[y];
          ~~~~~~~^
homecoming.cpp:23:17: warning: array subscript is below array bounds [-Warray-bounds]
   return C[y - 1] + C[n] - C[x - 1] + D[y];
          ~~~~~~~^
homecoming.cpp:23:17: warning: array subscript is below array bounds [-Warray-bounds]
   return C[y - 1] + C[n] - C[x - 1] + D[y];
          ~~~~~~~^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38