Submission #722238

#	Time	Username	Problem	Language	Result	Execution time	Memory
722238		mathematik	Catfish Farm (IOI22_fish)	C++17	0 / 100	280 ms	34200 KiB

fish

//#include "fish.h"

#include <bits/stdc++.h>
#define m 1000000
#define ll long long

using namespace std;

vector<pair<ll, ll>> best(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
  steg.push_back({m, 0});
  fish.push_back({m, 0});

  vector<pair<ll, ll>> erg;

  ll ind = 0, sum = 0;
  for (ll i = 0; i < fish.size(); i++)
  {
    while (steg[ind + 1].first < fish[i].first)
      ind++;
    
    erg.push_back({fish[i].first, steg[ind].second + sum});

    sum += fish[i].second;
  }
  
  return erg;
}

vector<pair<ll, ll>> collect(vector<pair<ll, ll>> scores, vector<pair<ll, ll>> fish) {
  // << "collect" << endl;
  //(scores);
  // << endl;
  //(fish);
  // << endl;
  
  scores.push_back({m, 0});
  fish.push_back({m, 0});

  vector<pair<ll, ll>> next;

  ll ind = 0;
  for (ll j = 0; j < fish.size(); j++)
  {
    while(scores[ind + 1].first < fish[j].first)
      ind++;
    next.push_back({fish[j].first - 1, scores[ind].second});
  }

  // << " -> " << endl;
  //(next);
  // << endl;

  return next;
}

vector<pair<ll, ll>> dp(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
  // << "dp" << endl;
  //(steg);
  // << endl;
  //(fish);

  steg.push_back({m, 0});
  fish.push_back({m, 0});

  vector<pair<ll, ll>> scores;
  
  ll score = 0, score_steg = 0;
  ll ind = 0, ind_steg = 0;
  ll h;

  while (ind + ind_steg < fish.size() + steg.size() - 2) {
    if (fish[ind].first < steg[ind_steg].first) {
      score += fish[ind].second;
      h = fish[ind++].first;
    } else {
      score_steg = steg[ind_steg].second;
      h = steg[ind_steg++].first;
    }
    if (score_steg > score)
      score = score_steg;
    scores.push_back({h, score});
  }

  // << " -> " << endl;
  //(scores);
  // << endl;

  return scores;
}

vector<pair<ll, ll>> inversion(vector<pair<ll, ll>> in, ll n) {
  vector<pair<ll, ll>> out;
  for (ll i = in.size() - 1; i >= 0; i--)
  {
    out.push_back({n - in[i].first, in[i].second});
  }
  return out;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  vector<vector<pair<ll, ll>>> vert(N);
  for (ll i = 0; i < M; i++)
  {
    vert[X[i]].push_back({Y[i], W[i]});
  }

  for (ll i = 0; i < N; i++)
  {
    vert[i].push_back({0, 0});
    sort(vert[i].begin(), vert[i].end());
  }
  
  vector<pair<ll, ll>> up, down;

  for (auto a: vert[0]) {
    up.push_back({a.first - 1, 0});
    down.push_back({a.first - 1, 0});
  }

  for (ll i = 0; i < N - 1; i++)
  {
    // << "up" << endl;
    //(up);
    // << endl;
    // << "down" << endl;
    //(down);
    // << endl << endl;

    // << i << " -> " << (i + 1) << endl;
    vector<pair<ll, ll>> next_up = collect(dp(up, vert[i]), vert[i + 1]);
    vector<pair<ll, ll>> next_down = collect(inversion(dp(inversion(down, N), inversion(vert[i + 1], N)), N), vert[i + 1]);

    // << "up" << endl;
    //(next_up);
    // << endl;
    // << "down" << endl;
    //(next_down);
    // << endl << endl << endl;

    for (ll j = 0; j < next_down.size(); j++)
    {
      next_down[j].second = max(next_down[j].second, next_up[j].second);
    }

    vector<pair<ll, ll>> best_zero = best(down, vert[i + 1]);
    for (ll j = 0; j < best_zero.size(); j++)
    {
      next_up[j].second = max(next_up[j].second, best_zero[j].second);
    }

    up = next_up;
    down = next_down;

    assert(up.size() == down.size());
    for (int i = 0; i < up.size(); i++)
    {
      assert(up[i].first == down[i].first);
    }
  }
  
  return max(down.front().second, up.back().second);
}

Compilation message (stderr)

fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > best(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:16:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (ll i = 0; i < fish.size(); i++)
      |                  ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > collect(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:42:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (ll j = 0; j < fish.size(); j++)
      |                  ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > dp(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:71:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   while (ind + ind_steg < fish.size() + steg.size() - 2) {
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:140:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (ll j = 0; j < next_down.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~
fish.cpp:146:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (ll j = 0; j < best_zero.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~
fish.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 0; i < up.size(); i++)
      |                     ~~^~~~~~~~~~~

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