oj.uz

Submission #1072495

# Submission time Handle Problem Language Result Execution time Memory
1072495 2024-08-23T20:30:38 Z Boas Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 2097152 KB 
#include "fish.h"

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

#pragma GCC optimize("Ofast")

#define loop(x, i) for (int i = 0; i < (x); i++)
#define loop1(x, i) for (int i = 1; i <= (x); i++)
#define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--)
#define itloop(x) for (auto it = begin(x); x != end(x); it++)
#define itrev(x) for (auto it = rbegin(x); x != rend(x); it++)
#define int long long
#define INF ((int64_t)(4e18 + 1))
#define INF32 ((int32_t)(2e9 + 1))
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define removeIn(x, l) l.erase(find(ALL(l), x))
#define pb push_back
#define sz(x) (int)(x).size()
#define F first
#define S second
#define var const auto &
#define foreach(l) for (var e : l)

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vii> vvii;
typedef vector<viii> vviii;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
typedef vector<si> vsi;
typedef vector<sii> vsii;
typedef vector<vsi> vvsi;
typedef vector<string> vstr;
typedef vector<vector<string>> vvstr;
typedef vector<bool> vb;
typedef vector<vb> vvb;

int max_weights(i32 N, i32 M, vi32 X, vi32 Y, vi32 W)
{
  if (M == 0)
    return 0;
  int yCount = *max_element(ALL(Y)) + 2;
  vvi wSum(N, vi(yCount));
  {
    vvi wsAtX(N, vi(yCount));
    loop(M, i)
    {
      wsAtX[X[i]][Y[i]] = W[i];
    }
    loop(N, x)
    {
      loop1(yCount - 1, y)
      {
        wSum[x][y] = wSum[x][y - 1] + wsAtX[x][y - 1];
      }
    }
  }
  vvvi dp(vvvi(yCount, vvi(yCount, vi(2))));  // 0: adjacentL, 1: adjacentR
  vvvi dp2(vvvi(yCount, vvi(yCount, vi(2)))); // 0: adjacentL, 1: adjacentR
  vi maxAll(N);
  vvi maxOfHeight(N, vi(yCount));
  loop(N, x)
  {
    vvi pMax1perJ(yCount, vi(yCount)); // dp[<=j][i][1]
    if (x != 0)
    {
      loop(yCount, j)
      {
        loop(yCount, i)
        {
          pMax1perJ[j][i] = max(j == 0 ? 0 : pMax1perJ[j - 1][i], dp[j][i][1]);
        }
      }
    }
    loop(yCount, j)
    {
      int prevMax = 0;
      if (x != 0)
      {
        loop(yCount, i)
        {
          prevMax = max(prevMax, dp[j][i][0]);
        }
      }
      loop(yCount, i) // hoogte van deze steiger
      {
        if (j <= i)
        {
          dp2[i][j][0] = dp2[i][j][1] = (x == 0) ? 0 : maxOfHeight[x - 1][i];
        }
        else
        {
          int sum = wSum[x][j] - wSum[x][i];
          if (x == 0)
          {
            dp2[i][j][0] = -1;
            dp2[i][j][1] = sum;
          }
          else
          {
            dp2[i][j][0] = max(dp[j][i][1], prevMax) + sum;
            dp2[i][j][1] = max(pMax1perJ[j][i], maxAll[x - 1]) + sum;
          }
        }
        maxAll[x] = max({maxAll[x], dp2[i][j][0]});
        maxOfHeight[x][j] = max({maxOfHeight[x][j], dp2[i][j][0], dp2[i][j][1]});
      }
    }
    dp = dp2;
  }
  return maxAll.back();
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 826 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Runtime error 886 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11960 KB Output is correct
2 Correct 24 ms 12080 KB Output is correct
3 Correct 32 ms 13076 KB Output is correct
4 Correct 33 ms 13620 KB Output is correct
5 Correct 57 ms 15956 KB Output is correct
6 Correct 48 ms 15412 KB Output is correct
7 Correct 44 ms 15920 KB Output is correct
8 Correct 43 ms 16016 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 530 ms 12552 KB Output is correct
16 Correct 7 ms 1116 KB Output is correct
17 Correct 492 ms 13632 KB Output is correct
18 Correct 465 ms 13600 KB Output is correct
19 Correct 460 ms 13584 KB Output is correct
20 Correct 455 ms 13936 KB Output is correct
21 Correct 114 ms 4920 KB Output is correct
22 Correct 504 ms 14752 KB Output is correct
23 Correct 460 ms 12880 KB Output is correct
24 Correct 449 ms 13344 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 472 ms 12756 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 530 ms 12552 KB Output is correct
16 Correct 7 ms 1116 KB Output is correct
17 Correct 492 ms 13632 KB Output is correct
18 Correct 465 ms 13600 KB Output is correct
19 Correct 460 ms 13584 KB Output is correct
20 Correct 455 ms 13936 KB Output is correct
21 Correct 114 ms 4920 KB Output is correct
22 Correct 504 ms 14752 KB Output is correct
23 Correct 460 ms 12880 KB Output is correct
24 Correct 449 ms 13344 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 472 ms 12756 KB Output is correct
27 Execution timed out 1106 ms 1198736 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11960 KB Output is correct
2 Correct 24 ms 12080 KB Output is correct
3 Correct 32 ms 13076 KB Output is correct
4 Correct 33 ms 13620 KB Output is correct
5 Correct 57 ms 15956 KB Output is correct
6 Correct 48 ms 15412 KB Output is correct
7 Correct 44 ms 15920 KB Output is correct
8 Correct 43 ms 16016 KB Output is correct
9 Runtime error 826 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 826 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -