oj.uz

Submission #1033479

# Submission time Handle Problem Language Result Execution time Memory
1033479 2024-07-24T22:08:50 Z Tonyl Catfish Farm (IOI22_fish) C++17
0 / 100
 35 ms 12744 KB 
#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;
  }
};

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(-1));
    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);
    }
  }

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

Compilation message

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++)
......
   51 |     REP(me, dp[x].size()) {
      |         ~~~~~~~~~~~~~~~~            
fish.cpp:51:5: note: in expansion of macro 'REP'
   51 |     REP(me, dp[x].size()) {
      |     ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 12744 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '2147458640'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7260 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7260 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 12744 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '2147458640'
2 Halted 0 ms 0 KB -