답안 #654783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654783	2022-11-01T15:37:09 Z	t6twotwo	메기 농장 (IOI22_fish)	C++17	18 / 100	264 ms	51480 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(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(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

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	29724 KB	Output is correct
2	Correct	88 ms	33944 KB	Output is correct
3	Correct	33 ms	23752 KB	Output is correct
4	Correct	34 ms	23780 KB	Output is correct
5	Correct	247 ms	51480 KB	Output is correct
6	Correct	264 ms	50744 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	170 ms	35496 KB	Output is correct
3	Correct	208 ms	43216 KB	Output is correct
4	Correct	81 ms	29548 KB	Output is correct
5	Correct	89 ms	33832 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	35 ms	23764 KB	Output is correct
11	Correct	35 ms	23716 KB	Output is correct
12	Correct	90 ms	30760 KB	Output is correct
13	Correct	104 ms	35164 KB	Output is correct
14	Correct	89 ms	29332 KB	Output is correct
15	Correct	113 ms	32504 KB	Output is correct
16	Correct	86 ms	29224 KB	Output is correct
17	Correct	99 ms	32392 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	23696 KB	Output is correct
2	Correct	36 ms	23892 KB	Output is correct
3	Correct	74 ms	28368 KB	Output is correct
4	Correct	63 ms	28308 KB	Output is correct
5	Correct	102 ms	36964 KB	Output is correct
6	Correct	105 ms	36244 KB	Output is correct
7	Correct	112 ms	36852 KB	Output is correct
8	Correct	105 ms	36816 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 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	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 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	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 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	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

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	23696 KB	Output is correct
2	Correct	36 ms	23892 KB	Output is correct
3	Correct	74 ms	28368 KB	Output is correct
4	Correct	63 ms	28308 KB	Output is correct
5	Correct	102 ms	36964 KB	Output is correct
6	Correct	105 ms	36244 KB	Output is correct
7	Correct	112 ms	36852 KB	Output is correct
8	Correct	105 ms	36816 KB	Output is correct
9	Correct	100 ms	36656 KB	Output is correct
10	Correct	87 ms	21504 KB	Output is correct
11	Correct	164 ms	42892 KB	Output is correct
12	Correct	1 ms	300 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	300 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	300 KB	Output is correct
18	Correct	33 ms	23764 KB	Output is correct
19	Correct	33 ms	23764 KB	Output is correct
20	Correct	35 ms	23692 KB	Output is correct
21	Incorrect	33 ms	23776 KB	1st lines differ - on the 1st token, expected: '1062016', found: '0'
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	29724 KB	Output is correct
2	Correct	88 ms	33944 KB	Output is correct
3	Correct	33 ms	23752 KB	Output is correct
4	Correct	34 ms	23780 KB	Output is correct
5	Correct	247 ms	51480 KB	Output is correct
6	Correct	264 ms	50744 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	170 ms	35496 KB	Output is correct
9	Correct	208 ms	43216 KB	Output is correct
10	Correct	81 ms	29548 KB	Output is correct
11	Correct	89 ms	33832 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	35 ms	23764 KB	Output is correct
17	Correct	35 ms	23716 KB	Output is correct
18	Correct	90 ms	30760 KB	Output is correct
19	Correct	104 ms	35164 KB	Output is correct
20	Correct	89 ms	29332 KB	Output is correct
21	Correct	113 ms	32504 KB	Output is correct
22	Correct	86 ms	29224 KB	Output is correct
23	Correct	99 ms	32392 KB	Output is correct
24	Correct	34 ms	23696 KB	Output is correct
25	Correct	36 ms	23892 KB	Output is correct
26	Correct	74 ms	28368 KB	Output is correct
27	Correct	63 ms	28308 KB	Output is correct
28	Correct	102 ms	36964 KB	Output is correct
29	Correct	105 ms	36244 KB	Output is correct
30	Correct	112 ms	36852 KB	Output is correct
31	Correct	105 ms	36816 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	0 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	-

답안 #654783

Compilation message