Submission #415146

#	Time	Username	Problem	Language	Result	Execution time	Memory
415146		schse	Meetings (IOI18_meetings)	C++17	4 / 100	5600 ms	504648 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#include "meetings.h"

vector<vector<long long>> prefsum;

long long calcscore(int l, int r, int p, std::vector<int> const &H)
{
  int mx = 0;
  long long sum = 0;
  for (int i = p; i <= r; i++)
  {
    mx = max(mx, H[i]);
    sum += mx;
  }
  mx = 0;
  for (int i = p; i >= l; i--)
  {
    mx = max(mx, H[i]);
    sum += mx;
  }
  sum -= H[p];
  assert(sum == prefsum[p][l] + prefsum[p][r] - H[p]);
  return sum;
}

long long findmin(int l, int r, std::vector<int> const &H)
{
  long long mx = INT64_MAX;
  for (int i = l; i <= r; i++)
  {
    mx = min(mx, calcscore(l, r, i, H));
  }
  return mx;
}

void calcpref(vector<int> const &H)
{
  prefsum.resize(H.size(), vector<long long>(H.size(), 0));
  for (int i = 0; i < H.size(); i++)
  {
    int mx = 0;
    long long sum = 0;
    for (int e = i; e < H.size(); e++)
    {
      mx = max(mx, H[e]);
      prefsum[i][e] = sum += mx;
    }
    mx = 0;
    sum = 0;
    for (int e = i; e >= 0; e--)
    {
      mx = max(mx, H[e]);
      prefsum[i][e] = sum += mx;
    }
  }
}

std::vector<long long> minimum_costs(std::vector<int> H,
                                     std::vector<int> L,
                                     std::vector<int> R)
{
  calcpref(H);

  int Q = L.size();
  std::vector<long long> C(Q);
  for (int j = 0; j < Q; ++j)
  {
    C[j] = findmin(L[j], R[j], H);
  }
  return C;
}

Compilation message (stderr)

meetings.cpp: In function 'void calcpref(const std::vector<int>&)':
meetings.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0; i < H.size(); i++)
      |                   ~~^~~~~~~~~~
meetings.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int e = i; e < H.size(); e++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40