oj.uz

Submission #628282

# Submission time Handle Problem Language Result Execution time Memory
628282 2022-08-13T09:32:00 Z 600Mihnea Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 69668 KB 
#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void maxup(ll &a, ll b) {
  a = max(a, b);
}

long long max_weights(int n, int cnt_fish, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW) {
  const ll inf = (ll) 1e18 + 7;
  n += 7;

  vector<set<int>> interestingSet(n);
  vector<vector<int>> interesting(n);
  vector<vector<vector<ll>>> dp(2, vector<vector<ll>> (n));
  vector<vector<ll>> both(n);
  vector<ll> dp_zero(n, 0LL);
  vector<vector<pair<int, ll>>> pe(n);

  assert((int) XX.size() == cnt_fish);
  assert((int) YY.size() == cnt_fish);
  assert((int) WW.size() == cnt_fish);


  for (int i = 0; i < cnt_fish; i++) {
    int x = XX[i] + 5, y = YY[i] + 1, w = WW[i];
    pe[x].push_back({y, w});
    vector<int> xs = {x - 1, x + 1};
    for (auto &i : xs) {
      interestingSet[i].insert(y);
    }
  }

  for (int x = 0; x < n; x++) {
    interestingSet[x].insert(0);
    for (auto &y : interestingSet[x]) {
      interesting[x].push_back(y);
    }
    dp[0][x].resize((int) interesting[x].size(), 0LL);
    dp[1][x].resize((int) interesting[x].size(), 0LL);
    both[x].resize((int) interesting[x].size(), 0LL);

    sort(pe[x].begin(), pe[x].end());
    ll sum = 0;
    for (auto &it : pe[x]) {
      sum += it.second;
      it.second = sum;
    }
  }

  function<ll(int, int)> get = [&] (int x, int y) {
    if (x == n) {
      return 0LL;
    }
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    ll sol = 0;
    int low = 0, high = (int) pe[x].size() - 1;

    while (low <= high) {
      int mid = (low + high) / 2;
      if (pe[x][mid].first <= y) {
        sol = pe[x][mid].second;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    return sol;
  };


  for (int i = 5; i < n - 2; i++) {
    {
      maxup(dp_zero[i], dp_zero[i - 1]);
      for (int ant_j = 0; ant_j < (int) interesting[i - 1].size(); ant_j++) {
        int h2 = interesting[i - 1][ant_j];
        maxup(dp_zero[i], both[i - 1][ant_j]);
      }
    }
    {
      int q = 0, w = 0;
      for (int j = 0; j < (int) interesting[i].size(); j++) {
        int h = interesting[i][j];
        while (q < (int) interesting[i - 2].size() && interesting[i - 2][q] < h) {
          q++;
        }
        while (w < (int) interesting[i - 1].size() && interesting[i - 1][w] < h) {
          w++;
        }
        ll dp_ant0 = 0, xx = -inf, yy = -inf;
        for (int ant_j = 0; ant_j < q; ant_j++) {
          maxup(xx, both[i - 2][ant_j]);
        }
        for (int ant_j = q; ant_j < (int) interesting[i - 2].size(); ant_j++) {
          int h2 = interesting[i - 2][ant_j];
          maxup(yy, both[i - 2][ant_j] + - get(i - 1, h2));
        }
        maxup(dp_ant0, max(xx + get(i + 1, h), yy + get(i - 1, h) + get(i + 1, h)));
        maxup(dp_ant0, dp_zero[i - 2] + get(i - 1, h) + get(i + 1, h));
        maxup(dp[0][i][j], dp_ant0);
        maxup(dp[1][i][j], dp_ant0);
        xx = -inf, yy = -inf;
        for (int ant_j = 0; ant_j < w; ant_j++) {
          int h2 = interesting[i - 1][ant_j];
          maxup(xx, dp[1][i - 1][ant_j] - get(i, h2) - get(i - 1, h2));
        }
        for (int ant_j = w; ant_j < (int) interesting[i - 1].size(); ant_j++) {
          maxup(yy, both[i - 1][ant_j]);
        }
        maxup(dp[1][i][j], xx + get(i - 1, h) + get(i + 1, h));
        maxup(dp[0][i][j], yy - get(i, h) + get(i + 1, h));
        both[i][j] = max(dp[0][i][j], dp[1][i][j]);
      }
    }
  }
  ll sol = 0;

  for (int i = 0; i < n; i++) {
    maxup(sol, dp_zero[i]);
    for (int j = 0; j < (int) interesting[i].size(); j++) {
      maxup(sol, both[i][j]);
    }
  }

  return sol;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:82:13: warning: unused variable 'h2' [-Wunused-variable]
   82 |         int h2 = interesting[i - 1][ant_j];
      |             ^~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 47860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1061 ms 62908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 34696 KB Output is correct
2 Correct 73 ms 34696 KB Output is correct
3 Correct 140 ms 37836 KB Output is correct
4 Correct 140 ms 38948 KB Output is correct
5 Correct 211 ms 44984 KB Output is correct
6 Correct 186 ms 45892 KB Output is correct
7 Correct 187 ms 46436 KB Output is correct
8 Correct 182 ms 46464 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 432 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 3 ms 468 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 432 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 1 ms 428 KB Output is correct
16 Correct 9 ms 596 KB Output is correct
17 Correct 618 ms 7520 KB Output is correct
18 Correct 543 ms 7500 KB Output is correct
19 Correct 330 ms 7592 KB Output is correct
20 Correct 245 ms 6932 KB Output is correct
21 Correct 239 ms 6828 KB Output is correct
22 Correct 983 ms 13504 KB Output is correct
23 Correct 37 ms 2248 KB Output is correct
24 Correct 304 ms 6036 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 31 ms 2044 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 432 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 1 ms 428 KB Output is correct
16 Correct 9 ms 596 KB Output is correct
17 Correct 618 ms 7520 KB Output is correct
18 Correct 543 ms 7500 KB Output is correct
19 Correct 330 ms 7592 KB Output is correct
20 Correct 245 ms 6932 KB Output is correct
21 Correct 239 ms 6828 KB Output is correct
22 Correct 983 ms 13504 KB Output is correct
23 Correct 37 ms 2248 KB Output is correct
24 Correct 304 ms 6036 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 31 ms 2044 KB Output is correct
27 Correct 5 ms 1748 KB Output is correct
28 Execution timed out 1063 ms 32680 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 34696 KB Output is correct
2 Correct 73 ms 34696 KB Output is correct
3 Correct 140 ms 37836 KB Output is correct
4 Correct 140 ms 38948 KB Output is correct
5 Correct 211 ms 44984 KB Output is correct
6 Correct 186 ms 45892 KB Output is correct
7 Correct 187 ms 46436 KB Output is correct
8 Correct 182 ms 46464 KB Output is correct
9 Correct 227 ms 50516 KB Output is correct
10 Correct 187 ms 28140 KB Output is correct
11 Correct 396 ms 54836 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 236 KB Output is correct
16 Correct 1 ms 236 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 74 ms 34708 KB Output is correct
19 Correct 75 ms 34608 KB Output is correct
20 Correct 62 ms 34744 KB Output is correct
21 Correct 82 ms 34736 KB Output is correct
22 Correct 293 ms 50992 KB Output is correct
23 Correct 498 ms 65656 KB Output is correct
24 Correct 535 ms 69668 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 47860 KB Time limit exceeded
2 Halted 0 ms 0 KB -