oj.uz

Submission #625411

# Submission time Handle Problem Language Result Execution time Memory
625411 2022-08-10T11:28:36 Z model_code Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 2097152 KB 
#include "fish.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 100100
#define MAXM 300300
 
vector<pair<int, int>> byx[MAXN];
vector<long long> sum[MAXN];
 
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  // Subtask 1.
  if (all_of(W.begin(), W.end(), [](int i) { return i % 2 == 0; })) {
    return accumulate(W.begin(), W.end(), 0LL);
  }
 
  for (int i = 0; i < M; i++) {
    byx[X[i]].emplace_back(Y[i], W[i]);
  }
 
  for (int x = 0; x < N; x++) {
    sort(byx[x].begin(), byx[x].end());
    sum[x].push_back(0);
    for (auto p : byx[x]) {
      sum[x].push_back(sum[x].back() + p.second);
    }
  }
 
  // Subtask 2.
  if (all_of(X.begin(), X.end(), [](int i) { return i <= 1; })) {
    return max(sum[0].back(), sum[1].back());
  }
 
  // Subtask 3 - 5.
  int maxy = (*max_element(Y.begin(), Y.end())) + 1;
  // dp[n][cur][prev]
  long long dp[N + 1][maxy + 1][maxy + 1] = {};
  long long dpmax[N + 1][maxy + 1] = {};
 
  for (int x = 1; x < N; x++) {
    long long wpreb = 0;
    int ipre = 0;
    for (int cur = 0; cur <= maxy; cur++) {
      if (ipre < byx[x - 1].size() && byx[x - 1][ipre].first == cur - 1) {
        wpreb += byx[x - 1][ipre].second;
        ipre++;
      }
      int jpre = 0;
      long long wcur = 0;
      int icur = 0;
      long long wpre = wpreb;
      for (int pre = 0; pre <= maxy; pre++) {
        if (icur < byx[x].size() && byx[x][icur].first == pre - 1) {
          if (pre > cur) {
            wcur += byx[x][icur].second;
          }
          icur++;
        }
        if (jpre < byx[x - 1].size() && byx[x - 1][jpre].first == pre - 1) {
          if (jpre < ipre) {
            wpre -= byx[x - 1][jpre].second;
          }
          jpre++;
        }
 
        if (pre == 0 && cur == 0) {
          // case 1: pre == 0 && cur == 0
          dp[x + 1][cur][pre] = dpmax[x][pre];
        }
        else if (cur == 0) {
          // case 2: pre > 0 && cur == 0
          dp[x + 1][cur][pre] = wcur + dpmax[x][pre];
        }
        else if (pre == 0) {
          // case 3: pre == 0 && cur > 0
          dp[x + 1][cur][pre] = dpmax[x][pre];
          int kpre = 0;
          long long wkpre = 0;
          for (int k = 0; k <= cur; k++) {
            if (kpre < byx[x - 1].size() && byx[x - 1][kpre].first == k - 1) {
              wkpre += byx[x - 1][kpre].second;
              kpre++;
            }
            dp[x + 1][cur][pre] = max(dp[x + 1][cur][pre], dp[x][pre][k] + wpre - wkpre);
          }
        }
        else {
          // case 4: pre > 0 && cur > 0
          dp[x + 1][cur][pre] = wpre + wcur + dp[x][pre][0];
        }
 
        dpmax[x + 1][cur] = max(dpmax[x + 1][cur], dp[x + 1][cur][pre]);
 
        // printf("dp[x = %d][cur = %d][pre = %d] = %lld (wpre = %lld, wcur = %lld)\n", x, cur, pre, dp[x + 1][cur][pre], wpre, wcur);
      }
    }
  }
 
  return *max_element(dpmax[N], dpmax[N] + maxy + 1);
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |       if (ipre < byx[x - 1].size() && byx[x - 1][ipre].first == cur - 1) {
      |           ~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (icur < byx[x].size() && byx[x][icur].first == pre - 1) {
      |             ~~~~~^~~~~~~~~~~~~~~
fish.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if (jpre < byx[x - 1].size() && byx[x - 1][jpre].first == pre - 1) {
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             if (kpre < byx[x - 1].size() && byx[x - 1][kpre].first == k - 1) {
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12260 KB Output is correct
2 Correct 64 ms 13740 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Execution timed out 1192 ms 1806584 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 21 ms 12756 KB Output is correct
3 Correct 69 ms 15852 KB Output is correct
4 Correct 39 ms 15200 KB Output is correct
5 Correct 108 ms 18228 KB Output is correct
6 Correct 59 ms 18220 KB Output is correct
7 Correct 74 ms 19952 KB Output is correct
8 Correct 58 ms 19832 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 21 ms 12756 KB Output is correct
3 Correct 69 ms 15852 KB Output is correct
4 Correct 39 ms 15200 KB Output is correct
5 Correct 108 ms 18228 KB Output is correct
6 Correct 59 ms 18220 KB Output is correct
7 Correct 74 ms 19952 KB Output is correct
8 Correct 58 ms 19832 KB Output is correct
9 Execution timed out 1073 ms 2097152 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12260 KB Output is correct
2 Correct 64 ms 13740 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Execution timed out 1192 ms 1806584 KB Time limit exceeded
6 Halted 0 ms 0 KB -