oj.uz

Submission #415149

# Submission time Handle Problem Language Result Execution time Memory
415149 2021-05-31T15:19:09 Z schse Meetings (IOI18_meetings) C++17
19 / 100
 3199 ms 786436 KB 
#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)
{
  return prefsum[p][l] + prefsum[p][r] - H[p];
}

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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 49 ms 70876 KB Output is correct
3 Correct 54 ms 70860 KB Output is correct
4 Correct 55 ms 70808 KB Output is correct
5 Correct 57 ms 70852 KB Output is correct
6 Correct 50 ms 70900 KB Output is correct
7 Correct 49 ms 70812 KB Output is correct
8 Correct 49 ms 70844 KB Output is correct
9 Correct 55 ms 70852 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 49 ms 70876 KB Output is correct
3 Correct 54 ms 70860 KB Output is correct
4 Correct 55 ms 70808 KB Output is correct
5 Correct 57 ms 70852 KB Output is correct
6 Correct 50 ms 70900 KB Output is correct
7 Correct 49 ms 70812 KB Output is correct
8 Correct 49 ms 70844 KB Output is correct
9 Correct 55 ms 70852 KB Output is correct
10 Correct 299 ms 196336 KB Output is correct
11 Correct 459 ms 196424 KB Output is correct
12 Correct 295 ms 196480 KB Output is correct
13 Correct 599 ms 196416 KB Output is correct
14 Correct 331 ms 196428 KB Output is correct
15 Correct 368 ms 196420 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3199 ms 504668 KB Output is correct
3 Runtime error 530 ms 786436 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3199 ms 504668 KB Output is correct
3 Runtime error 530 ms 786436 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 49 ms 70876 KB Output is correct
3 Correct 54 ms 70860 KB Output is correct
4 Correct 55 ms 70808 KB Output is correct
5 Correct 57 ms 70852 KB Output is correct
6 Correct 50 ms 70900 KB Output is correct
7 Correct 49 ms 70812 KB Output is correct
8 Correct 49 ms 70844 KB Output is correct
9 Correct 55 ms 70852 KB Output is correct
10 Correct 299 ms 196336 KB Output is correct
11 Correct 459 ms 196424 KB Output is correct
12 Correct 295 ms 196480 KB Output is correct
13 Correct 599 ms 196416 KB Output is correct
14 Correct 331 ms 196428 KB Output is correct
15 Correct 368 ms 196420 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3199 ms 504668 KB Output is correct
18 Runtime error 530 ms 786436 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -