oj.uz

Submission #659589

# Submission time Handle Problem Language Result Execution time Memory
659589 2022-11-18T17:18:22 Z peijar Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 6828 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 301;
const int INF = 1e18;

int dp[MAXN][MAXN][2];

int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y,
                vector<signed> W) {

  if (N > MAXN)
    return 0;
  vector<vector<pair<int, int>>> onCol(N);
  vector<vector<int>> prefSum(N);
  for (int i = 0; i < M; ++i)
    onCol[X[i]].emplace_back(Y[i] + 1, W[i]);
  for (int i = 0; i < N; ++i) {
    sort(onCol[i].begin(), onCol[i].end());
    prefSum[i].resize(onCol[i].size() + 1);
    for (int j = 0; j < (int)onCol[i].size(); ++j)
      prefSum[i][j + 1] = prefSum[i][j] + onCol[i][j].second;
  }

  int sol = 0;
  for (int i = 1; i < N; ++i)
    for (int h = 0; h <= N; ++h) {
      // 1
      for (int oldH = h + 1; oldH <= N; ++oldH) {
        int lo = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h, INF)) -
                 onCol[i].begin();
        int up =
            upper_bound(onCol[i].begin(), onCol[i].end(), pair(oldH, INF)) -
            onCol[i].begin();
        dp[i][h][1] =
            max(dp[i][h][1], prefSum[i][up] - prefSum[i][lo] +
                                 max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
      }
      // 0
      for (int oldH = 0; oldH <= N; ++oldH) {
        if (oldH >= h)
          dp[i][h][0] =
              max(dp[i][h][0], max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
        else {
          int lo = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
                               pair(oldH, INF)) -
                   onCol[i - 1].begin();
          int up = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
                               pair(h, INF)) -
                   onCol[i - 1].begin();
          dp[i][h][0] =
              max(dp[i][h][0],
                  dp[i - 1][oldH][0] + prefSum[i - 1][up] - prefSum[i - 1][lo]);
        }
      }
      sol = max({sol, dp[i][h][0], dp[i][h][1]});
    }
  return sol;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2124 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
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 Incorrect 44 ms 4000 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 43 ms 984 KB Output is correct
10 Correct 393 ms 1832 KB Output is correct
11 Correct 46 ms 1004 KB Output is correct
12 Correct 338 ms 1720 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 351 ms 1756 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 43 ms 984 KB Output is correct
10 Correct 393 ms 1832 KB Output is correct
11 Correct 46 ms 1004 KB Output is correct
12 Correct 338 ms 1720 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 351 ms 1756 KB Output is correct
15 Correct 225 ms 1636 KB Output is correct
16 Correct 12 ms 724 KB Output is correct
17 Correct 954 ms 3996 KB Output is correct
18 Correct 870 ms 4512 KB Output is correct
19 Correct 859 ms 4452 KB Output is correct
20 Correct 859 ms 4376 KB Output is correct
21 Correct 968 ms 4308 KB Output is correct
22 Execution timed out 1097 ms 6828 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 43 ms 984 KB Output is correct
10 Correct 393 ms 1832 KB Output is correct
11 Correct 46 ms 1004 KB Output is correct
12 Correct 338 ms 1720 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 351 ms 1756 KB Output is correct
15 Correct 225 ms 1636 KB Output is correct
16 Correct 12 ms 724 KB Output is correct
17 Correct 954 ms 3996 KB Output is correct
18 Correct 870 ms 4512 KB Output is correct
19 Correct 859 ms 4452 KB Output is correct
20 Correct 859 ms 4376 KB Output is correct
21 Correct 968 ms 4308 KB Output is correct
22 Execution timed out 1097 ms 6828 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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