제출 #69715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69715		octopuses	Homecoming (BOI18_homecoming)	C++17	0 / 100	132 ms	75120 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], a[N], A[N], B[N];
int S[N], b[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] = 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] + 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);
  }
  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]);
    answer = max(answer, a[i]);
    if(a[i] < 0)
      continue;
    S[i] += k - 1;
    if(S[i] > n) S[i] -= n;
    if(S[i] < i)
    {
      b[0] ++;
      b[n + 1] --;
    }
    b[S[i] + 1] --;
    b[i] ++;
  }
  for(int i = 1; i <= n; ++ i)
    b[i] += b[i - 1];
  int l = 1;
  for(int i = n; i >= 1; -- i)
    if(b[i] == 0)
    {
      l = i + 1;
      break;
    }
  if(l == n + 1) l = 1;
  for(int i = 1; i <= n; ++ i)
  {
    if(b[i] == 0 && i != l)
    {
      int p = i - 1 - k + 1;
      if(p < 1) p += n;
      tot += F(l, p);
      l = i + 1;
    }
  }
  answer = max(answer, tot);
  return answer;
}
/*
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
*/

컴파일 시 표준 에러 (stderr) 메시지

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:41:15: warning: array subscript is above array bounds [-Warray-bounds]
   answer = C[N];
            ~~~^
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