제출 #1033485

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

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define D(x) cerr << #x << ": " << x << endl;

struct Event {
  int height;
  int belowFish = 0;
  int pure = 0;
  int help = 0;

  Event(int h, int b = 0) : height(h), belowFish(b) {}

  bool operator<(Event &other) {
    return height < other.height;
  }

  void debug() {
    assert(help >= pure);
    cerr << height << " (" << belowFish << "): " << help << "/" << pure << endl; 
  }
};

const int MAX_N = 100001;
vector<Event> dp[MAX_N];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  REP(i,M) {
    int x = X[i];
    int y = Y[i];
    int w = W[i];
    dp[x].push_back(Event(y-1, w));
    if (x != 0) dp[x-1].push_back(Event(y));
    if (x != N-1) dp[x+1].push_back(Event(y));
  }

  REP(x,N) {
    dp[x].push_back(Event(-2));
    dp[x].push_back(Event(N));
    sort(all(dp[x]));
  }

  for (int x = 1; x < N; x++) {
    int top_default = 0;
    trav(e, dp[x-1]) top_default = max(top_default, e.help);

    // pure
    int lf = 0; int maxlf = dp[x-1].size()-1;
    int sofar = 0;
    REP(me, dp[x].size()) {
      while (lf != maxlf && dp[x-1][lf+1].height < dp[x][me].height) {
        lf++;
        sofar = max(sofar, dp[x-1][lf].pure);
        sofar += dp[x-1][lf].belowFish;
      }
      dp[x][me].pure = max(top_default, sofar);
    }

    // with help
    lf = maxlf;
    sofar = 0;
    for (int me = dp[x].size()-1; me >= 0; me--) {
      while (lf != 0 && dp[x-1][lf-1].height > dp[x][me].height) {
        lf--;
        sofar = max(sofar, dp[x-1][lf].help);
      }
      sofar += dp[x][me].belowFish;
      dp[x][me].help = max(dp[x][me].pure, sofar);
    }
  }

  /*for (int x = 0; x < N; x++) {
    D(x);
    trav(e, dp[x]) e.debug();
  }*/

  int abs_top = 0;
  trav(e, dp[N-1]) abs_top = max(abs_top, e.help); 
  return abs_top;
}

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

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define REP(i,n) for (int i = 0; i < n; i++)
......
   56 |     REP(me, dp[x].size()) {
      |         ~~~~~~~~~~~~~~~~            
fish.cpp:56:5: note: in expansion of macro 'REP'
   56 |     REP(me, dp[x].size()) {
      |     ^~~

• 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