제출 #722216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722216		mathematik	메기 농장 (IOI22_fish)	C++17	0 / 100	209 ms	24624 KiB

fish

//#include "fish.h"

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

using namespace std;

void print(vector<pair<int, int>> v) {
  //for (pair<int, int> p: v)
    // << p.first << " " << p.second << endl;
}

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

  vector<pair<int, int>> erg;

  int ind = 0, sum = 0;
  for (int 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<int, int>> collect(vector<pair<int, int>> scores, vector<pair<int, int>> fish) {
  // << "collect" << endl;
  print(scores);
  // << endl;
  print(fish);
  // << endl;
  
  scores.push_back({m, 0});
  fish.push_back({m, 0});

  vector<pair<int, int>> next;

  int ind = 0;
  for (int 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;
  print(next);
  // << endl;

  return next;
}

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

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

  vector<pair<int, int>> scores;
  
  int score = 0, score_steg = 0;
  int ind = 0, ind_steg = 0;
  int 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;
  print(scores);
  // << endl;

  return scores;
}

vector<pair<int, int>> inversion(vector<pair<int, int>> in, int n) {
  vector<pair<int, int>> out;
  for (int 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<int, int>>> vert(N);
  for (int i = 0; i < M; i++)
  {
    vert[X[i]].push_back({Y[i], W[i]});
  }

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

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

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

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

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

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

    vector<pair<int, int>> best_zero = best(down, vert[i + 1]);
    for (int 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;
  }
  
  return max(down.front().second, up.back().second);
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'std::vector<std::pair<int, int> > best(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
fish.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int i = 0; i < fish.size(); i++)
      |                   ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<int, int> > collect(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
fish.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (int j = 0; j < fish.size(); j++)
      |                   ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<int, int> > dp(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
fish.cpp:75:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   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:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int j = 0; j < next_down.size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~
fish.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int j = 0; j < best_zero.size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~

• 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