Submission #626663

#	Time	Username	Problem	Language	Result	Execution time	Memory
626663		ITO	Catfish Farm (IOI22_fish)	C++17	100 / 100	166 ms	22260 KiB

fish

#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++;
      }
      if (k >= 2 && v[i - 1][k - 1].first == v[i][j].first) {
        ru[p0].push_back(max(te + v[i - 1][k - 2].second, rd[p1][0]));
      } else {
        ru[p0].push_back(max(te + v[i - 1][k - 1].second, rd[p1][0]));
      }
      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) {
        if (v[i - 1][k].first > v[i][j].first) {
          te = max(te, rd[p1][k] + v[i][j].second);
        } else {
          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);
    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 (stderr)

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:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i = 0; i < ru[p1].size(); i++) co = max(co, max(ru[p1][i], rd[p1][i]));
      |                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16