oj.uz

Submission #628294

# Submission time Handle Problem Language Result Execution time Memory
628294 2022-08-13T09:36:16 Z 600Mihnea Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 68332 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;
      ll Fpref = -inf, Spref = -inf;
      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) {
          maxup(Fpref, both[i - 2][q]);
          q++;
        }
        while (w < (int) interesting[i - 1].size() && interesting[i - 1][w] < h) {
          int h2 = interesting[i - 1][w];
          maxup(Spref, dp[1][i - 1][w] - get(i, h2) - get(i - 1, h2));
          w++;
        }
        ll dp_ant0 = 0, yy = -inf;
        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(Fpref + 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);
        yy = -inf;
        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], Spref + 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 1094 ms 46476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34660 KB Output is correct
2 Correct 57 ms 34736 KB Output is correct
3 Correct 106 ms 36904 KB Output is correct
4 Correct 88 ms 38604 KB Output is correct
5 Correct 159 ms 44804 KB Output is correct
6 Correct 152 ms 44828 KB Output is correct
7 Correct 161 ms 44984 KB Output is correct
8 Correct 159 ms 45008 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 207 ms 6704 KB Output is correct
18 Correct 196 ms 6848 KB Output is correct
19 Correct 138 ms 6804 KB Output is correct
20 Correct 103 ms 6220 KB Output is correct
21 Correct 98 ms 6208 KB Output is correct
22 Correct 350 ms 11992 KB Output is correct
23 Correct 21 ms 2004 KB Output is correct
24 Correct 122 ms 5516 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 19 ms 1924 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 207 ms 6704 KB Output is correct
18 Correct 196 ms 6848 KB Output is correct
19 Correct 138 ms 6804 KB Output is correct
20 Correct 103 ms 6220 KB Output is correct
21 Correct 98 ms 6208 KB Output is correct
22 Correct 350 ms 11992 KB Output is correct
23 Correct 21 ms 2004 KB Output is correct
24 Correct 122 ms 5516 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 19 ms 1924 KB Output is correct
27 Correct 4 ms 1748 KB Output is correct
28 Execution timed out 1093 ms 30476 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34660 KB Output is correct
2 Correct 57 ms 34736 KB Output is correct
3 Correct 106 ms 36904 KB Output is correct
4 Correct 88 ms 38604 KB Output is correct
5 Correct 159 ms 44804 KB Output is correct
6 Correct 152 ms 44828 KB Output is correct
7 Correct 161 ms 44984 KB Output is correct
8 Correct 159 ms 45008 KB Output is correct
9 Correct 201 ms 49572 KB Output is correct
10 Correct 144 ms 26888 KB Output is correct
11 Correct 303 ms 53668 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 59 ms 34752 KB Output is correct
19 Correct 53 ms 34636 KB Output is correct
20 Correct 55 ms 34656 KB Output is correct
21 Correct 53 ms 34724 KB Output is correct
22 Correct 248 ms 50692 KB Output is correct
23 Correct 413 ms 65188 KB Output is correct
24 Correct 419 ms 68332 KB Output is correct

Subtask #8
0 / 16.0

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