Submission #69619

#	Time	Username	Problem	Language	Result	Execution time	Memory
69619		octopuses	Homecoming (BOI18_homecoming)	C++17	0 / 100	85 ms	12516 KiB

homecoming

//Giorgi Kldiashvili

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

#define ll long long


using namespace std;

const int N = 2000020;

int n;
ll C[N], D[N];
ll answer;
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 A[], int B[])
{
  n = NN;
  for(int i = n; i >= 1; -- i)
  {
    A[i] = A[i - 1];
    B[i] = B[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] + C[i];
  answer = C[N];
  for(int i = 1; i < k; ++ i) D[n] -= B[i];
  D[n] += A[n] - B[n];
  int r = k - 1;
  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);
  }
  if(d.size())
    answer = max(answer, F(1, d.back()));
  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);
    answer = max(answer, F(i, d.back()));
  }
  return answer;
}
/*
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:36:15: warning: array subscript is above array bounds [-Warray-bounds]
   answer = C[N];
            ~~~^
homecoming.cpp:22:17: warning: array subscript is below array bounds [-Warray-bounds]
   return C[y - 1] + C[n] - C[x - 1] + D[y];
          ~~~~~~~^
homecoming.cpp:22:17: warning: array subscript is below array bounds [-Warray-bounds]
   return C[y - 1] + C[n] - C[x - 1] + D[y];
          ~~~~~~~^
homecoming.cpp:22: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