oj.uz

Submission #626581

# Submission time Handle Problem Language Result Execution time Memory
626581 2022-08-11T14:44:52 Z ITO Catfish Farm (IOI22_fish) C++17
3 / 100
 158 ms 21828 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] - v[i - 1][0].second;
    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].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 (int 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].second);
        k--;
      }
      rd[p0][j] = max(rd[p0][j], te - v[i][j].second);
    }
    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:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   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 51 ms 12356 KB Output is correct
2 Correct 56 ms 14120 KB Output is correct
3 Correct 21 ms 7236 KB Output is correct
4 Correct 19 ms 7252 KB Output is correct
5 Correct 133 ms 21828 KB Output is correct
6 Correct 158 ms 21700 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 88 ms 16832 KB Output is correct
3 Correct 99 ms 19724 KB Output is correct
4 Correct 47 ms 12348 KB Output is correct
5 Correct 62 ms 14112 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 18 ms 7228 KB Output is correct
11 Correct 17 ms 7252 KB Output is correct
12 Correct 48 ms 12400 KB Output is correct
13 Correct 57 ms 14176 KB Output is correct
14 Correct 47 ms 12132 KB Output is correct
15 Correct 54 ms 13256 KB Output is correct
16 Incorrect 47 ms 12080 KB 1st lines differ - on the 1st token, expected: '40504176225961', found: '40503547457600'
17 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7252 KB Output is correct
2 Correct 17 ms 7292 KB Output is correct
3 Incorrect 46 ms 10024 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7252 KB Output is correct
2 Correct 17 ms 7292 KB Output is correct
3 Incorrect 46 ms 10024 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 51 ms 12356 KB Output is correct
2 Correct 56 ms 14120 KB Output is correct
3 Correct 21 ms 7236 KB Output is correct
4 Correct 19 ms 7252 KB Output is correct
5 Correct 133 ms 21828 KB Output is correct
6 Correct 158 ms 21700 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 88 ms 16832 KB Output is correct
9 Correct 99 ms 19724 KB Output is correct
10 Correct 47 ms 12348 KB Output is correct
11 Correct 62 ms 14112 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 18 ms 7228 KB Output is correct
17 Correct 17 ms 7252 KB Output is correct
18 Correct 48 ms 12400 KB Output is correct
19 Correct 57 ms 14176 KB Output is correct
20 Correct 47 ms 12132 KB Output is correct
21 Correct 54 ms 13256 KB Output is correct
22 Incorrect 47 ms 12080 KB 1st lines differ - on the 1st token, expected: '40504176225961', found: '40503547457600'
23 Halted 0 ms 0 KB -