Submission #625408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625408	2022-08-10T11:28:24 Z	model_code	Catfish Farm (IOI22_fish)	C++17	23 / 100	585 ms	97112 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;

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, it_col = 0, it_col1 = 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);
      while (it_col+1 < static_cast<int>(compressed_column[col].size()) &&
              compressed_column[col][it_col+1].first <= y_current_previously_covered) {
        it_col++;
      }
      int current_previously_covered = it_col;
      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);
      while (it_col1+1 < static_cast<int>(compressed_column[col-1].size()) &&
              compressed_column[col-1][it_col1+1].first <= y_bef_already_covered) {
        it_col1++;
      }
      int bef_already_covered = it_col1;
      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	113 ms	77776 KB	Output is correct
2	Correct	128 ms	80916 KB	Output is correct
3	Correct	55 ms	73828 KB	Output is correct
4	Correct	71 ms	73828 KB	Output is correct
5	Incorrect	322 ms	97112 KB	1st lines differ - on the 1st token, expected: '149814460735479', found: '166101698145179'
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	54980 KB	Output is correct
2	Incorrect	279 ms	82572 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	67 ms	73860 KB	Output is correct
2	Correct	53 ms	73752 KB	Output is correct
3	Correct	141 ms	76952 KB	Output is correct
4	Correct	107 ms	77236 KB	Output is correct
5	Correct	240 ms	83768 KB	Output is correct
6	Correct	261 ms	84544 KB	Output is correct
7	Correct	270 ms	84964 KB	Output is correct
8	Correct	273 ms	85208 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	54976 KB	Output is correct
2	Correct	32 ms	55064 KB	Output is correct
3	Correct	30 ms	55076 KB	Output is correct
4	Correct	31 ms	55012 KB	Output is correct
5	Correct	38 ms	55016 KB	Output is correct
6	Correct	26 ms	54984 KB	Output is correct
7	Correct	30 ms	55028 KB	Output is correct
8	Correct	29 ms	55024 KB	Output is correct
9	Incorrect	36 ms	55124 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	34 ms	54976 KB	Output is correct
2	Correct	32 ms	55064 KB	Output is correct
3	Correct	30 ms	55076 KB	Output is correct
4	Correct	31 ms	55012 KB	Output is correct
5	Correct	38 ms	55016 KB	Output is correct
6	Correct	26 ms	54984 KB	Output is correct
7	Correct	30 ms	55028 KB	Output is correct
8	Correct	29 ms	55024 KB	Output is correct
9	Incorrect	36 ms	55124 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	34 ms	54976 KB	Output is correct
2	Correct	32 ms	55064 KB	Output is correct
3	Correct	30 ms	55076 KB	Output is correct
4	Correct	31 ms	55012 KB	Output is correct
5	Correct	38 ms	55016 KB	Output is correct
6	Correct	26 ms	54984 KB	Output is correct
7	Correct	30 ms	55028 KB	Output is correct
8	Correct	29 ms	55024 KB	Output is correct
9	Incorrect	36 ms	55124 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	67 ms	73860 KB	Output is correct
2	Correct	53 ms	73752 KB	Output is correct
3	Correct	141 ms	76952 KB	Output is correct
4	Correct	107 ms	77236 KB	Output is correct
5	Correct	240 ms	83768 KB	Output is correct
6	Correct	261 ms	84544 KB	Output is correct
7	Correct	270 ms	84964 KB	Output is correct
8	Correct	273 ms	85208 KB	Output is correct
9	Correct	184 ms	83760 KB	Output is correct
10	Correct	318 ms	75756 KB	Output is correct
11	Correct	504 ms	96416 KB	Output is correct
12	Correct	24 ms	54968 KB	Output is correct
13	Correct	36 ms	55032 KB	Output is correct
14	Correct	25 ms	54996 KB	Output is correct
15	Correct	33 ms	55072 KB	Output is correct
16	Correct	38 ms	55080 KB	Output is correct
17	Correct	35 ms	55032 KB	Output is correct
18	Correct	67 ms	73840 KB	Output is correct
19	Correct	59 ms	73804 KB	Output is correct
20	Correct	52 ms	73860 KB	Output is correct
21	Correct	53 ms	73784 KB	Output is correct
22	Correct	251 ms	83552 KB	Output is correct
23	Correct	585 ms	96404 KB	Output is correct
24	Correct	548 ms	96152 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	77776 KB	Output is correct
2	Correct	128 ms	80916 KB	Output is correct
3	Correct	55 ms	73828 KB	Output is correct
4	Correct	71 ms	73828 KB	Output is correct
5	Incorrect	322 ms	97112 KB	1st lines differ - on the 1st token, expected: '149814460735479', found: '166101698145179'
6	Halted	0 ms	0 KB	-

Submission #625408

Compilation message