제출 #69745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69745		octopuses	Homecoming (BOI18_homecoming)	C++17	0 / 100	341 ms	194780 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], 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] + 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]);
    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(i == n) pre = 1;
    while(tt --)
    {
      T[now] = max(T[now], T[pre]);
      T[now] = max(T[now], a[now] + T[S[now]]);
      answer = max(answer, T[now]);
      pre --; if(pre == n - 1) pre = n;
      now --; if(now == n - 1) now = n;
    }
  }
  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