oj.uz

Submission #1033485

# Submission time Handle Problem Language Result Execution time Memory
1033485 2024-07-24T22:16:41 Z Tonyl Catfish Farm (IOI22_fish) C++17
0 / 100
 75 ms 19868 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;
  }

  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;
}

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++)
......
   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.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 12728 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 Correct 1 ms 2652 KB Output is correct
2 Incorrect 75 ms 19868 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '2147479781'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7256 KB Output is correct
2 Correct 9 ms 7512 KB Output is correct
3 Incorrect 32 ms 14416 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '2147479351'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2600 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '2145010650'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2600 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '2145010650'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2600 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '2145010650'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7256 KB Output is correct
2 Correct 9 ms 7512 KB Output is correct
3 Incorrect 32 ms 14416 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '2147479351'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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