Submission #654785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
654785	2022-11-01T15:42:06 Z	t6twotwo	Catfish Farm (IOI22_fish)	C++17	18 / 100	247 ms	45420 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = -(1LL << 60);
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  vector<vector<int>> b(n);
  for (int i = 0; i < m; i++) {
    b[x[i]].push_back(i);
  }
  vector d(n, vector<int>{-1});
  vector<vector<int>> r(n), p(n);
  for (int i = 0; i < n; i++) {
    sort(b[i].begin(), b[i].end(), [&](int j, int k) {
      return y[j] < y[k];
    });
    for (int j : b[i]) {
      r[i].push_back(y[j]);
      p[i].push_back(w[j]);
      if (i > 0) {
        d[i - 1].push_back(y[j]);
      }
      if (i < n - 1) {
        d[i + 1].push_back(y[j]);
      }
    }
  }
  vector<vector<long long>> ssum(n), psum(n);
  for (int i = 0; i < n; i++) {
    int k = p[i].size();
    psum[i] = vector<long long>(k + 1);
    ssum[i] = vector<long long>(k + 1);
    for (int j = 0; j < k; j++) {
      psum[i][j + 1] = psum[i][j] + p[i][j];
    }
    for (int j = k - 1; j >= 0; j--) {
      ssum[i][j] = ssum[i][j + 1] + p[i][j];
    }
  }
  auto suf_sum = [&](int i, int x) -> long long {
    if (i == -1) {
      return 0;
    }
    return ssum[i][upper_bound(r[i].begin(), r[i].end(), x) - r[i].begin()];
  };
  auto pre_sum = [&](int i, int x) -> long long {
    if (i == -1) {
      return 0;
    }
    return psum[i][upper_bound(r[i].begin(), r[i].end(), x) - r[i].begin()];
  };
  vector<int> e{-1};
  vector<array<long long, 2>> dp{{0, 0}};
  for (int i = 0; i < n; i++) {
    auto pd = dp;
    int l = d[i].size();
    dp = vector(l, array<long long, 2>{inf, inf});
    int k = pd.size();
    vector<long long> pmax(k + 1, inf);
    for (int j = 0; j < k; j++) {
      pmax[j + 1] = max(pmax[j], pd[j][0] + suf_sum(i - 1, e[j]));
    }
    vector<long long> smax(k + 1, inf);
    for (int j = k - 1; j >= 0; j--) {
      smax[j] = max(smax[j + 1], max(pd[j][0], pd[j][1]) - suf_sum(i, e[j]));
    }
    for (int j = 0; j < k; j++) {
      dp[0][0] = max(dp[0][0], max(pd[j][0], pd[j][1]));
      dp[0][1] = max(dp[0][1], max(pd[j][0], pd[j][1]) + pre_sum(i, d[i][j]));
    }
    for (int j = 1; j < l; j++) {
      dp[j][0] = max({dp[j][0], max(pd[0][1], pd[0][0] + pre_sum(i - 1, d[i][j])), pmax[upper_bound(e.begin(), e.end(), d[i][j]) - e.begin()] - suf_sum(i - 1, d[i][j])});
      dp[j][1] = max({dp[j][1], max(pd[0][1], pd[0][0] + pre_sum(i - 1, d[i][j])), smax[lower_bound(e.begin(), e.end(), d[i][j]) - e.begin()] + suf_sum(i, d[i][j])});
    }
    swap(e, d[i]);
  }
  long long ans = 0;
  for (auto v : dp) {
    ans = max(ans, max(v[0], v[1]));
  }
  return ans;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	28376 KB	Output is correct
2	Correct	88 ms	32320 KB	Output is correct
3	Correct	33 ms	23792 KB	Output is correct
4	Correct	34 ms	23764 KB	Output is correct
5	Correct	225 ms	45420 KB	Output is correct
6	Correct	247 ms	44260 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	158 ms	34620 KB	Output is correct
3	Correct	183 ms	39980 KB	Output is correct
4	Correct	78 ms	28376 KB	Output is correct
5	Correct	88 ms	32340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	35 ms	23748 KB	Output is correct
11	Correct	35 ms	23776 KB	Output is correct
12	Correct	83 ms	29500 KB	Output is correct
13	Correct	102 ms	33660 KB	Output is correct
14	Correct	84 ms	28000 KB	Output is correct
15	Correct	103 ms	31132 KB	Output is correct
16	Correct	83 ms	28084 KB	Output is correct
17	Correct	91 ms	31052 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	23764 KB	Output is correct
2	Correct	34 ms	23796 KB	Output is correct
3	Correct	68 ms	27732 KB	Output is correct
4	Correct	56 ms	27980 KB	Output is correct
5	Correct	97 ms	35544 KB	Output is correct
6	Correct	92 ms	35520 KB	Output is correct
7	Correct	100 ms	35404 KB	Output is correct
8	Correct	98 ms	35448 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 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	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '283601981870'
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 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	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '283601981870'
12	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	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 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	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '283601981870'
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	23764 KB	Output is correct
2	Correct	34 ms	23796 KB	Output is correct
3	Correct	68 ms	27732 KB	Output is correct
4	Correct	56 ms	27980 KB	Output is correct
5	Correct	97 ms	35544 KB	Output is correct
6	Correct	92 ms	35520 KB	Output is correct
7	Correct	100 ms	35404 KB	Output is correct
8	Correct	98 ms	35448 KB	Output is correct
9	Correct	102 ms	35484 KB	Output is correct
10	Correct	88 ms	19860 KB	Output is correct
11	Correct	152 ms	39384 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	34 ms	23764 KB	Output is correct
19	Correct	33 ms	23764 KB	Output is correct
20	Correct	32 ms	23764 KB	Output is correct
21	Incorrect	34 ms	23764 KB	1st lines differ - on the 1st token, expected: '1062016', found: '0'
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	28376 KB	Output is correct
2	Correct	88 ms	32320 KB	Output is correct
3	Correct	33 ms	23792 KB	Output is correct
4	Correct	34 ms	23764 KB	Output is correct
5	Correct	225 ms	45420 KB	Output is correct
6	Correct	247 ms	44260 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	158 ms	34620 KB	Output is correct
9	Correct	183 ms	39980 KB	Output is correct
10	Correct	78 ms	28376 KB	Output is correct
11	Correct	88 ms	32340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	35 ms	23748 KB	Output is correct
17	Correct	35 ms	23776 KB	Output is correct
18	Correct	83 ms	29500 KB	Output is correct
19	Correct	102 ms	33660 KB	Output is correct
20	Correct	84 ms	28000 KB	Output is correct
21	Correct	103 ms	31132 KB	Output is correct
22	Correct	83 ms	28084 KB	Output is correct
23	Correct	91 ms	31052 KB	Output is correct
24	Correct	35 ms	23764 KB	Output is correct
25	Correct	34 ms	23796 KB	Output is correct
26	Correct	68 ms	27732 KB	Output is correct
27	Correct	56 ms	27980 KB	Output is correct
28	Correct	97 ms	35544 KB	Output is correct
29	Correct	92 ms	35520 KB	Output is correct
30	Correct	100 ms	35404 KB	Output is correct
31	Correct	98 ms	35448 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	2 ms	468 KB	Output is correct
42	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '283601981870'
43	Halted	0 ms	0 KB	-

Submission #654785

Compilation message