Submission #625407

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625407	2022-08-10T11:28:20 Z	model_code	Catfish Farm (IOI22_fish)	C++17	23 / 100	803 ms	98752 KB

fish

#include "fish.h"

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

const int kMaxN = 100'000;
const int kMaxFishInColumn = 3;

vector<pair<int, long long>> compressed_cover[kMaxN];
vector<pair<int, long long>> compressed_column[kMaxN];
long long dp[kMaxN][2*kMaxFishInColumn+2][2*kMaxFishInColumn+2];
int N;

int getColumnIdx(int col, int y) {
  pair<int, long long> temp = {y+1, 0};
  auto it = lower_bound(compressed_column[col].begin(), compressed_column[col].end(), temp);
  return it - compressed_column[col].begin() - 1;
}

long long solve(int col, int bef2, int bef) {
  if (col == N) {
    return 0;
  }

  long long &ret = dp[col][bef2][bef];
  if (ret != -1) {
    return ret;
  }

  for (int i = 0 ; i < static_cast<int>(compressed_cover[col].size()) ; i++) {
    long long add = compressed_cover[col][i].second;
    if (col > 0) {
      int y_current_previously_covered = compressed_cover[col][i].first;
      y_current_previously_covered = min(y_current_previously_covered, compressed_cover[col-1][bef].first);
      int current_previously_covered = getColumnIdx(col, y_current_previously_covered);
      add -= compressed_column[col][current_previously_covered].second;

      int y_bef_already_covered = compressed_cover[col-1][bef].first;
      if (bef2 > 0) y_bef_already_covered = max(y_bef_already_covered, compressed_cover[col-2][bef2].first);
      y_bef_already_covered = min(y_bef_already_covered, compressed_cover[col][i].first);
      int bef_already_covered = getColumnIdx(col-1, y_bef_already_covered);
      add -= compressed_column[col-1][bef_already_covered].second;
    }
    ret = max(ret, add + solve(col+1, bef, i));
  }

  return ret;
}

long long max_weights(int _N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  N = _N;
  for (int i = 0 ; i < M ; i++) {
    if (X[i] > 0) compressed_cover[X[i]-1].push_back({Y[i]+1, W[i]});
    if (X[i]+1 < N) compressed_cover[X[i]+1].push_back({Y[i]+1, W[i]});
    compressed_column[X[i]].push_back({Y[i]+1, W[i]});
  }


  for (int i = 0 ; i < N ; i++) {
    auto preparePrefixSum = [](vector<pair<int, long long>> &psum) {
      psum.push_back({0, 0ll});
      sort(psum.begin(), psum.end());
      for (int j = 1 ; j < static_cast<int>(psum.size()) ; j++) {
        psum[j].second += psum[j-1].second;
      }
    };

    preparePrefixSum(compressed_column[i]);
    preparePrefixSum(compressed_cover[i]);
  }


  memset(dp, -1, sizeof dp);
  long long ret = solve(0, 0, 0);
  return ret;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	76328 KB	Output is correct
2	Correct	153 ms	79448 KB	Output is correct
3	Correct	58 ms	72220 KB	Output is correct
4	Correct	64 ms	72232 KB	Output is correct
5	Incorrect	367 ms	98752 KB	1st lines differ - on the 1st token, expected: '149814460735479', found: '165791652318107'
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	54996 KB	Output is correct
2	Incorrect	803 ms	83452 KB	1st lines differ - on the 1st token, expected: '40604614618209', found: '40513855087053'
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	72276 KB	Output is correct
2	Correct	58 ms	72284 KB	Output is correct
3	Correct	118 ms	76048 KB	Output is correct
4	Correct	108 ms	75752 KB	Output is correct
5	Correct	202 ms	82232 KB	Output is correct
6	Correct	201 ms	83040 KB	Output is correct
7	Correct	293 ms	83600 KB	Output is correct
8	Correct	247 ms	82040 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	55012 KB	Output is correct
2	Correct	28 ms	55056 KB	Output is correct
3	Correct	31 ms	55032 KB	Output is correct
4	Correct	33 ms	54996 KB	Output is correct
5	Correct	42 ms	55076 KB	Output is correct
6	Correct	26 ms	55060 KB	Output is correct
7	Correct	35 ms	54984 KB	Output is correct
8	Correct	36 ms	55048 KB	Output is correct
9	Incorrect	28 ms	55168 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '218786778485'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	55012 KB	Output is correct
2	Correct	28 ms	55056 KB	Output is correct
3	Correct	31 ms	55032 KB	Output is correct
4	Correct	33 ms	54996 KB	Output is correct
5	Correct	42 ms	55076 KB	Output is correct
6	Correct	26 ms	55060 KB	Output is correct
7	Correct	35 ms	54984 KB	Output is correct
8	Correct	36 ms	55048 KB	Output is correct
9	Incorrect	28 ms	55168 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '218786778485'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	55012 KB	Output is correct
2	Correct	28 ms	55056 KB	Output is correct
3	Correct	31 ms	55032 KB	Output is correct
4	Correct	33 ms	54996 KB	Output is correct
5	Correct	42 ms	55076 KB	Output is correct
6	Correct	26 ms	55060 KB	Output is correct
7	Correct	35 ms	54984 KB	Output is correct
8	Correct	36 ms	55048 KB	Output is correct
9	Incorrect	28 ms	55168 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '218786778485'
10	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	72276 KB	Output is correct
2	Correct	58 ms	72284 KB	Output is correct
3	Correct	118 ms	76048 KB	Output is correct
4	Correct	108 ms	75752 KB	Output is correct
5	Correct	202 ms	82232 KB	Output is correct
6	Correct	201 ms	83040 KB	Output is correct
7	Correct	293 ms	83600 KB	Output is correct
8	Correct	247 ms	82040 KB	Output is correct
9	Correct	293 ms	82188 KB	Output is correct
10	Correct	340 ms	74972 KB	Output is correct
11	Correct	620 ms	94744 KB	Output is correct
12	Correct	29 ms	55020 KB	Output is correct
13	Correct	35 ms	55040 KB	Output is correct
14	Correct	35 ms	55040 KB	Output is correct
15	Correct	41 ms	54972 KB	Output is correct
16	Correct	38 ms	55088 KB	Output is correct
17	Correct	26 ms	54980 KB	Output is correct
18	Correct	64 ms	72176 KB	Output is correct
19	Correct	58 ms	72292 KB	Output is correct
20	Correct	62 ms	72296 KB	Output is correct
21	Correct	55 ms	72208 KB	Output is correct
22	Correct	300 ms	81992 KB	Output is correct
23	Correct	635 ms	94836 KB	Output is correct
24	Correct	685 ms	96416 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	76328 KB	Output is correct
2	Correct	153 ms	79448 KB	Output is correct
3	Correct	58 ms	72220 KB	Output is correct
4	Correct	64 ms	72232 KB	Output is correct
5	Incorrect	367 ms	98752 KB	1st lines differ - on the 1st token, expected: '149814460735479', found: '165791652318107'
6	Halted	0 ms	0 KB	-

Submission #625407

Compilation message