oj.uz

Submission #1028114

# Submission time Handle Problem Language Result Execution time Memory
1028114 2024-07-19T13:52:01 Z NeroZein Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 51144 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#pragma GCC target("avx2,fma")
 
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  vector<vector<pair<int, int>>> in_col(N);
  for (int i = 0; i < M; ++i) {
    in_col[X[i]].push_back({Y[i], W[i]});
  }
  for (int i = 0; i < N; ++i) {
    sort(in_col[i].begin(), in_col[i].end());
    in_col[i].push_back({N, 0});
  }
  vector<vector<long long>> pre(N);
  for (int col = 1; col < N; ++col) {
    pre[col].resize(in_col[col].size());
    for (int i = 0; i < (int) in_col[col].size(); ++i) {
      int ptr = 0; 
      long long sum = 0; 
      while (ptr < (int) in_col[col - 1].size() && in_col[col - 1][ptr].first < in_col[col][i].first) {
        sum += in_col[col - 1][ptr].second; 
        ptr++; 
      }
      pre[col][i] = sum; 
    }
  }
  vector<vector<long long>> nxt(N);
  for (int col = 0; col < N - 1; ++col) {
    nxt[col].resize(in_col[col].size());
    for (int i = 0; i < (int) in_col[col].size(); ++i) {//M tot
      int ptr = 0;
      long long sum = 0;
      while (ptr < (int) in_col[col + 1].size() && in_col[col + 1][ptr].first < in_col[col][i].first) {
        sum += in_col[col + 1][ptr].second;
        ptr++;
      }
      nxt[col][i] = sum; 
    }
  }
  vector<vector<vector<long long>>> dp(N + 1);
  for (int i = 0; i < N + 1; ++i) {
    dp[i].resize(2);
    dp[i][0].assign(2, -1);
    dp[i][1].assign(2, -1);
  }
  dp[0][0][0] = 0;  
  for (int col = 0; col < N; ++col) {
    int sz = (int) in_col[col].size();
    for (int f = 0; f < 2; ++f) {
      for (int f2 = 0; f2 < 2; ++f2) {
        if (dp[col][f][f2] == -1) {
          continue; 
        }
        if (f) {
          long long s = 0; 
          for (int i = 0; i < sz; ++i) {
            long long w = s;
            if (col < N - 1) {
              w += nxt[col][i];
            }
            dp[col + 1][1][0] = max(dp[col + 1][1][0], dp[col][f][f2] + w);
            s -= in_col[col][i].second; 
          }
          dp[col + 1][0][0] = max(dp[col + 1][0][0], dp[col][f][f2]);
        } else {
          long long s = 0;
          for (int i = 0; i < sz; ++i) {
            long long w = s; 
            if (f2) {
              w += pre[col][i];
            }
            dp[col + 1][0][1] = max(dp[col + 1][0][1], dp[col][f][f2] + w); 
            s -= in_col[col][i].second; 
          }
          s = 0;
          if (col < N - 1) {
            s = nxt[col][sz - 1];
          }
          if (f2) {
            s += pre[col][sz - 1]; 
          }
          dp[col + 1][1][0] = max(dp[col + 1][1][0], dp[col][f][f2] + s);
        }
      }
    }
  }
  long long ans = 0;
  for (int f = 0; f < 2; ++f) {
    for (int f2 = 0; f2 < 2; ++f2) {
      ans = max(ans, dp[N][f][f2]); 
    }
  }
  return ans; 
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 32968 KB Output is correct
2 Correct 76 ms 37400 KB Output is correct
3 Correct 44 ms 31580 KB Output is correct
4 Correct 44 ms 31572 KB Output is correct
5 Correct 128 ms 51088 KB Output is correct
6 Correct 138 ms 51144 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 31568 KB Output is correct
2 Correct 44 ms 31576 KB Output is correct
3 Correct 52 ms 30800 KB Output is correct
4 Correct 54 ms 33108 KB Output is correct
5 Correct 71 ms 35664 KB Output is correct
6 Correct 73 ms 35156 KB Output is correct
7 Correct 70 ms 35408 KB Output is correct
8 Correct 73 ms 35412 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 344 KB Output is correct
6 Correct 0 ms 344 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 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 344 KB Output is correct
6 Correct 0 ms 344 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 43 ms 3336 KB Output is correct
18 Correct 48 ms 3668 KB Output is correct
19 Correct 32 ms 3420 KB Output is correct
20 Correct 32 ms 3508 KB Output is correct
21 Correct 32 ms 3420 KB Output is correct
22 Correct 101 ms 6740 KB Output is correct
23 Correct 4 ms 1112 KB Output is correct
24 Correct 17 ms 2396 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 4 ms 972 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 344 KB Output is correct
6 Correct 0 ms 344 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 43 ms 3336 KB Output is correct
18 Correct 48 ms 3668 KB Output is correct
19 Correct 32 ms 3420 KB Output is correct
20 Correct 32 ms 3508 KB Output is correct
21 Correct 32 ms 3420 KB Output is correct
22 Correct 101 ms 6740 KB Output is correct
23 Correct 4 ms 1112 KB Output is correct
24 Correct 17 ms 2396 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 4 ms 972 KB Output is correct
27 Correct 2 ms 1372 KB Output is correct
28 Correct 417 ms 15264 KB Output is correct
29 Execution timed out 1020 ms 18768 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 31568 KB Output is correct
2 Correct 44 ms 31576 KB Output is correct
3 Correct 52 ms 30800 KB Output is correct
4 Correct 54 ms 33108 KB Output is correct
5 Correct 71 ms 35664 KB Output is correct
6 Correct 73 ms 35156 KB Output is correct
7 Correct 70 ms 35408 KB Output is correct
8 Correct 73 ms 35412 KB Output is correct
9 Correct 71 ms 35396 KB Output is correct
10 Correct 50 ms 20848 KB Output is correct
11 Correct 115 ms 41556 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 432 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 428 KB Output is correct
18 Correct 43 ms 31540 KB Output is correct
19 Correct 43 ms 31576 KB Output is correct
20 Correct 44 ms 31572 KB Output is correct
21 Correct 47 ms 31580 KB Output is correct
22 Correct 74 ms 36652 KB Output is correct
23 Correct 104 ms 41552 KB Output is correct
24 Correct 106 ms 41796 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 32968 KB Output is correct
2 Correct 76 ms 37400 KB Output is correct
3 Correct 44 ms 31580 KB Output is correct
4 Correct 44 ms 31572 KB Output is correct
5 Correct 128 ms 51088 KB Output is correct
6 Correct 138 ms 51144 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1088 ms 15960 KB Time limit exceeded
9 Halted 0 ms 0 KB -