oj.uz

Submission #707662

# Submission time Handle Problem Language Result Execution time Memory
707662 2023-03-09T17:05:11 Z Johann Catfish Farm (IOI22_fish) C++17
75 / 100
 1000 ms 112520 KB 
#include "fish.h"

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef map<ll, ll> mii;
typedef vector<mii> vmii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 3e5 * 1e9 + 100;

void updateIdx(ll y, ll &ny, mii::iterator &itpref0, ll &pref0)
{
  if (itpref0->first == y)
  {
    pref0 = itpref0->second;
    ++itpref0;
  }
  ny = min(itpref0->first, ny);
}

void eraseDuplicates(mii &dp, int N)
{
  ll y = 0, lastY;
  ll lastV = -1;
  while (y < N)
  {
    auto it = dp.lower_bound(y);
    do
    {
      lastV = it->second, lastY = it->first;
      ++it;
      if (it == dp.end())
        return;

    } while (lastV != it->second);
    dp.erase(it);
    y = lastY;
  }
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
  vmii grid(N + 4); // becomes prefix grid
  for (int x = 0; x < sz(grid); ++x)
    grid[x][0] = 0;

  for (int i = 0; i < M; ++i)
    grid[X[i] + 3][Y[i]] = W[i];

  for (int x = 0; x < sz(grid); ++x)
  {
    ll pref = 0;
    for (auto it = grid[x].begin(); it != grid[x].end(); ++it)
    {
      pref += it->second;
      it->second = pref;
    }
    grid[x][N] = pref;
  }

  vmii dpg(sz(grid));  // growth stack thing
  vmii dp(sz(grid));   // normal all dp
  vi dpm(sz(grid), 0); // maximum einer Spaltes
  for (int i = 0; i < 3; ++i)
    dpg[i][0] = dpg[i][N] = dp[i][0] = dp[i][N] = 0;

  for (int x = 3; x < sz(grid) - 1; ++x) // so i choose the borders
  {
    ll c1 = -INF, c2 = -INF; // running variables for case 1 and 2 // TODO: INIT
    ll y = 0, ny;
    ll pref0 = 0, pref1 = 0, pref2 = 0, dp0 = 0, dpg1 = 0;
    auto itpref0 = grid[x - 1].begin(); // idx for pref x-1
    auto itpref1 = grid[x].begin();     // idx for pref x
    auto itpref2 = grid[x + 1].begin(); // idx for pref x+1
    auto itdp0 = dp[x - 2].begin();     // idx for dp x-2
    auto itdpg1 = dpg[x - 1].begin();   // idx for dpg x-1
    while (y < N)
    {
      // update indices
      ny = INT_MAX;
      updateIdx(y, ny, itpref0, pref0);
      updateIdx(y, ny, itpref1, pref1);
      updateIdx(y, ny, itpref2, pref2);
      updateIdx(y, ny, itdp0, dp0);
      updateIdx(y, ny, itdpg1, dpg1);

      // Case 1 - last tower in x-1 and smaller y
      c1 = max(c1, dpg1 - pref0 - pref1);
      dpg[x][y] = max(dpg[x][y], pref0 + pref2 + c1);

      // Case 2 - last tower in x-2 and smaller y
      c2 = max(c2, dp0 - pref0);
      dpg[x][y] = max(dpg[x][y], pref0 + pref2 + c2);

      // Case 3 - last tower in x-1 and larger y (or if it is smaller, case 1 performs better)
      // here the last tower might be larger than the current one
      dp[x][y] = max(dp[x][y], dpm[x - 1] - pref1 + pref2);

      // Case 4 - Last Tower in x-2 and larger y (or if it is smaller, case 2 performs better)
      dpg[x][y] = max(dpg[x][y], dpm[x - 2] + pref2);

      // Case 5 - Last Tower in x-3
      dpg[x][y] = max(dpg[x][y], dpm[x - 3] + pref0 + pref2);

      // keep track for dpg & dpm
      dp[x][y] = max(dp[x][y], dpg[x][y]);
      dpm[x] = max(dpm[x], dp[x][y]);

      y = ny;
    }
    eraseDuplicates(dp[x], N);
    eraseDuplicates(dpg[x], N);
    dp[x][N] = max(dp[x][N], dp[x].rbegin()->second);
    dpg[x][N] = max(dpg[x][N], dpg[x].rbegin()->second);
  }

  return *max_element(all(dpm));
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 69800 KB Output is correct
2 Correct 965 ms 81868 KB Output is correct
3 Correct 70 ms 52684 KB Output is correct
4 Correct 70 ms 52712 KB Output is correct
5 Execution timed out 1087 ms 95880 KB Time limit exceeded
6 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 Correct 949 ms 82068 KB Output is correct
3 Execution timed out 1052 ms 85988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 52668 KB Output is correct
2 Correct 73 ms 52812 KB Output is correct
3 Correct 81 ms 48936 KB Output is correct
4 Correct 81 ms 53740 KB Output is correct
5 Correct 99 ms 55228 KB Output is correct
6 Correct 92 ms 55244 KB Output is correct
7 Correct 97 ms 55328 KB Output is correct
8 Correct 103 ms 55268 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 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 468 KB Output is correct
10 Correct 2 ms 824 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 2 ms 596 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 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 468 KB Output is correct
10 Correct 2 ms 824 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 3 ms 872 KB Output is correct
17 Correct 76 ms 11156 KB Output is correct
18 Correct 64 ms 10464 KB Output is correct
19 Correct 57 ms 10460 KB Output is correct
20 Correct 53 ms 10076 KB Output is correct
21 Correct 53 ms 10004 KB Output is correct
22 Correct 132 ms 19536 KB Output is correct
23 Correct 20 ms 3000 KB Output is correct
24 Correct 56 ms 8264 KB Output is correct
25 Correct 2 ms 724 KB Output is correct
26 Correct 15 ms 2740 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 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 468 KB Output is correct
10 Correct 2 ms 824 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 3 ms 872 KB Output is correct
17 Correct 76 ms 11156 KB Output is correct
18 Correct 64 ms 10464 KB Output is correct
19 Correct 57 ms 10460 KB Output is correct
20 Correct 53 ms 10076 KB Output is correct
21 Correct 53 ms 10004 KB Output is correct
22 Correct 132 ms 19536 KB Output is correct
23 Correct 20 ms 3000 KB Output is correct
24 Correct 56 ms 8264 KB Output is correct
25 Correct 2 ms 724 KB Output is correct
26 Correct 15 ms 2740 KB Output is correct
27 Correct 6 ms 2644 KB Output is correct
28 Correct 408 ms 52616 KB Output is correct
29 Correct 981 ms 82716 KB Output is correct
30 Correct 906 ms 88748 KB Output is correct
31 Correct 935 ms 88580 KB Output is correct
32 Correct 522 ms 66932 KB Output is correct
33 Correct 956 ms 89412 KB Output is correct
34 Correct 943 ms 89628 KB Output is correct
35 Correct 245 ms 33996 KB Output is correct
36 Correct 882 ms 85496 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 52668 KB Output is correct
2 Correct 73 ms 52812 KB Output is correct
3 Correct 81 ms 48936 KB Output is correct
4 Correct 81 ms 53740 KB Output is correct
5 Correct 99 ms 55228 KB Output is correct
6 Correct 92 ms 55244 KB Output is correct
7 Correct 97 ms 55328 KB Output is correct
8 Correct 103 ms 55268 KB Output is correct
9 Correct 239 ms 80232 KB Output is correct
10 Correct 104 ms 39988 KB Output is correct
11 Correct 233 ms 79824 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 300 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 67 ms 52636 KB Output is correct
19 Correct 65 ms 52648 KB Output is correct
20 Correct 64 ms 52704 KB Output is correct
21 Correct 68 ms 52712 KB Output is correct
22 Correct 289 ms 85740 KB Output is correct
23 Correct 389 ms 108596 KB Output is correct
24 Correct 444 ms 112520 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 69800 KB Output is correct
2 Correct 965 ms 81868 KB Output is correct
3 Correct 70 ms 52684 KB Output is correct
4 Correct 70 ms 52712 KB Output is correct
5 Execution timed out 1087 ms 95880 KB Time limit exceeded
6 Halted 0 ms 0 KB -