oj.uz

Submission #69814

# Submission time Handle Problem Language Result Execution time Memory
69814 2018-08-21T14:38:55 Z octopuses Homecoming (BOI18_homecoming) C++17
0 / 100
 41 ms 8992 KB 
//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] = T[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]));
  a[1] = F(1, S[1]);
  S[1] += k;
  if(S[1] > n)
    S[1] -= n;
  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)
  {
    if(a[i] <= 0) continue;
    T[S[i]] = max(a[i], T[S[i]]);
    int pre = i - 1; if(pre == 0) pre = n;
    int nex = i + 1; if(nex == n + 1) nex = 1;
    if(S[i] == pre && S[nex] == i)
      return answer;
  }
  tot = 0;
  for(int i = 1; i <= n; ++ i)
    tot += T[i];
  answer = max(answer, tot);
  return answer;
}

Compilation message

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];
          ~~~~~~~^
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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 832 KB Output is correct
3 Incorrect 4 ms 832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 832 KB Output is correct
3 Incorrect 4 ms 832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 8992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 832 KB Output is correct
3 Incorrect 4 ms 832 KB Output isn't correct
4 Halted 0 ms 0 KB -