oj.uz

Submission #626609

# Submission time Handle Problem Language Result Execution time Memory
626609 2022-08-11T15:03:30 Z ITO Catfish Farm (IOI22_fish) C++17
3 / 100
 172 ms 21812 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  vector<vector<pair<int, ll>>> v(N, vector<pair<int, ll>>(0));
  vector<ll> ru[2], rd[2];
  int p0 = 1, p1 = 0;
  ll co = 0;

  for (int i = 0; i < M; i++) {
    v[X[i]].push_back({Y[i], W[i]});
  }
  for (int i = 0; i < N; i++) {
    v[i].push_back({0, 0});
    v[i].push_back({N, 0});
    sort(v[i].begin(), v[i].end());
    for (int j = 1; j < v[i].size(); j++) v[i][j].second += v[i][j - 1].second;
  }
  for (int j = 0; j < v[0].size(); j++) {
    ru[0].push_back(0);
    rd[0].push_back(0);
  }
  for (int i = 1; i < N; i++) {
    ru[p0].clear();
    rd[p0].clear();
    int j, k = 1;
    ll te = ru[p1][0];
    for (j = 0; j < v[i].size(); j++) {
      while (k < v[i - 1].size() && v[i - 1][k].first <= v[i][j].first) {
        te = max(te, ru[p1][k] - v[i - 1][k - 1].second);
        k++;
      }
      ru[p0].push_back(te + v[i - 1][k - 1].second);
      rd[p0].push_back(ru[p0].back());
    }
    k = v[i - 1].size() - 2;
    te = rd[p1].back() + v[i].back().second;
    for (j = v[i].size() - 1; j > 0; j--) {
      while (k >= 0 && v[i - 1][k].first >= v[i][j].first) {
        te = max(te, rd[p1][k] + v[i][j - 1].second);
        k--;
      }
      rd[p0][j] = max(rd[p0][j], te - v[i][j - 1].second);
    }
    while (k >= 0 && v[i - 1][k].first >= v[i][j].first) {
      te = max(te, rd[p1][k]);
      k--;
    }
    rd[p0][0] = max(rd[p0][0], te);
    ru[p0][0] = max(ru[p0][0], rd[p1][0]);
    swap(p0, p1);
  }
  for (int i = 0; i < ru[p1].size(); i++) co = max(co, max(ru[p1][i], rd[p1][i]));
  return co;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 1; j < v[i].size(); j++) v[i][j].second += v[i][j - 1].second;
      |                     ~~^~~~~~~~~~~~~
fish.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (int j = 0; j < v[0].size(); j++) {
      |                   ~~^~~~~~~~~~~~~
fish.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (j = 0; j < v[i].size(); j++) {
      |                 ~~^~~~~~~~~~~~~
fish.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |       while (k < v[i - 1].size() && v[i - 1][k].first <= v[i][j].first) {
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < ru[p1].size(); i++) co = max(co, max(ru[p1][i], rd[p1][i]));
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12364 KB Output is correct
2 Correct 55 ms 14208 KB Output is correct
3 Correct 17 ms 7252 KB Output is correct
4 Correct 20 ms 7252 KB Output is correct
5 Correct 128 ms 21812 KB Output is correct
6 Correct 172 ms 21616 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 79 ms 16828 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7252 KB Output is correct
2 Correct 20 ms 7232 KB Output is correct
3 Incorrect 37 ms 9952 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7252 KB Output is correct
2 Correct 20 ms 7232 KB Output is correct
3 Incorrect 37 ms 9952 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12364 KB Output is correct
2 Correct 55 ms 14208 KB Output is correct
3 Correct 17 ms 7252 KB Output is correct
4 Correct 20 ms 7252 KB Output is correct
5 Correct 128 ms 21812 KB Output is correct
6 Correct 172 ms 21616 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 79 ms 16828 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929'
9 Halted 0 ms 0 KB -