Submission #723008

#	Time	Username	Problem	Language	Result	Execution time	Memory
723008		mathematik	Catfish Farm (IOI22_fish)	C++17	0 / 100	98 ms	15588 KiB

fish

#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 + 1, 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) {
  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});
  }

  return next;
}

vector<pair<ll, ll>> dp2(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> 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 > 0 | ind_steg > 0) {
    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});
  }

  return scores;
}

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

  vector<pair<ll, ll>> scores;
  
  ll score = 0, score_steg = 0;
  ll ind = fish.size() - 1, ind_steg = steg.size() - 1;
  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});
  }

  return scores;
}

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++)
  {
    vector<pair<ll, ll>> next_up = collect(dp(up, vert[i]), vert[i + 1]);
    vector<pair<ll, ll>> next_down = collect(dp2(down, vert[i + 1]), vert[i + 1]);

    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:14: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]
   14 |   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:34: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]
   34 |   for (ll j = 0; j < fish.size(); j++)
      |                  ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > dp2(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:54:14: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   54 |   while (ind > 0 | ind_steg > 0) {
      |          ~~~~^~~
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:80: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]
   80 |   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:121: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]
  121 |     for (ll j = 0; j < next_down.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~
fish.cpp:127: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]
  127 |     for (ll j = 0; j < best_zero.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~
fish.cpp:136: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]
  136 |     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