#include "fish.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
i64 table[3005][3005][3];
i64 table2[100005][5][3];
i64 val[3005][3005];
i64 val2[100005][5];
i64 psum[3005][3005];
i64 psum2[100005][5];
int n;
// type == 0 desc, type == 1 desc top, type == 2 asc
i64 dp(int x, int y, int type)
{
if (x >= n + 1)
return 0;
if (table[x][y][type] != -1)
return table[x][y][type];
auto& res = table[x][y][type];
res = 0;
if (type == 2)
{
// 한 칸 더 위 or 오른쪽 위 or 두칸 뛰면서 desc
if (y < n)
{
res = max(res, val[x][y] + dp(x, y + 1, type));
if (x < n - 1)
res = max(res, val[x][y] + dp(x + 1, y + 1, type));
}
res = max({ res, val[x][y] + dp(x + 2, y, 1), val[x][y] + dp(x + 3, y, 1) });
}
else if (type == 1)
{
// 내 아래 다 먹고 여기부터 asc로 전환 가능
if (x <= n - 1)
{
auto down = y == 0 ? 0 : psum[x][y - 1];
res = dp(x, y, 2) + down;
}
// 그 외의 경우, 그냥 단순 내림차
res = max(res, dp(x, y, 0));
}
else
{
// 단순 내림차 -> 한칸 밑으로 or 오른쪽 한칸 밑으로
if (y == 0)
{
// 맨밑 왔으면 그냥 한칸 옆으로 가면 됨
res = dp(x + 1, y, 1);
return res;
}
if (x < n - 1 && y < n)
res = max(res, psum[x][y] + dp(x + 1, y + 1, 2));
res = val[x][y] + max({ dp(x + 1, y - 1, 1), dp(x, y - 1, 0), psum[x][y - 1] + dp(x + 2, y, 1), psum[x][y-1] + dp(x + 3, y, 1) });
}
return res;
}
i64 sub1(vector<int> w)
{
i64 res = 0;
for (auto& wi : w)
res += wi;
return res;
}
i64 sub2(int m, vector<int> x, vector<int> y, vector<int> w)
{
i64 res1 = 0, res2 = 0;
for (int i = 0; i < m; i++)
{
if (x[i] == 0)
res1 += w[i];
else
res2 += w[i];
}
if (n <= 2)
return max(res1, res2);
i64 sums[2][100005] = { 0, };
for (int i = 0; i < m; i++)
sums[x[i]][y[i]] += w[i];
for (int xi = 0; xi < 2; xi++)
for (int yi = 1; yi < n; yi++)
sums[xi][yi] += sums[xi][yi - 1];
i64 res = max(res1, res2);
for (int y = 0; y < n; y++)
res = max(res, sums[0][y] + res2 - sums[1][y]);
return res;
}
i64 dp2(int x, int y, int type)
{
if (x >= n + 1)
return 0;
if (table2[x][y][type] != -1)
return table2[x][y][type];
auto& res = table2[x][y][type];
res = 0;
if (type == 2)
{
// 한 칸 더 위 or 오른쪽 위 or 두칸 뛰면서 desc
if (y < 2)
{
res = max(res, val2[x][y] + dp2(x, y + 1, type));
if (x < n - 1)
res = max(res, val2[x][y] + dp2(x + 1, y + 1, type));
}
res = max({ res, val2[x][y] + dp2(x + 2, y, 1), val2[x][y] + dp2(x + 3, y, 1) });
}
else if (type == 1)
{
// 내 아래 다 먹고 여기부터 asc로 전환 가능
if (x <= n - 1)
{
auto down = y == 0 ? 0 : psum2[x][y - 1];
res = dp2(x, y, 2) + down;
}
// 그 외의 경우, 그냥 단순 내림차
res = max(res, dp2(x, y, 0));
}
else
{
// 단순 내림차 -> 한칸 밑으로 or 오른쪽 한칸 밑으로
if (y == 0)
{
// 맨밑 왔으면 그냥 한칸 옆으로 가면 됨
res = dp2(x + 1, y, 1);
return res;
}
if (x < n - 1 && y < 2)
res = max(res, psum2[x][y] + dp2(x + 1, y + 1, 2));
res = val2[x][y] + max({ dp2(x + 1, y - 1, 1), dp2(x, y - 1, 0), psum2[x][y - 1] + dp2(x + 2, y, 1), psum2[x][y - 1] + dp2(x + 3, y, 1) });
}
return res;
}
i64 sub3(int m, vector<int> x, vector<int> y, vector<int> w)
{
for (int i = 0; i < m; i++)
val2[x[i] + 1][y[i] + 1] += w[i];
for (int x = 1; x <= n; x++)
for (int y = 1; y <= 2; y++)
psum2[x][y] += psum2[x][y - 1] + val2[x][y];
memset(table2, -1, sizeof(table2));
return dp2(0, 0, 1);
}
i64 max_weights(int n_, int m, vector<int> x, vector<int> y, vector<int> w)
{
n = n_;
if (all_of(all(x), [](int xi) { return xi % 2 == 0; }))
return sub1(w);
if (all_of(all(x), [](int xi) { return xi <= 1; }))
return sub2(m, x, y, w);
if (all_of(all(y), [](int yi) { return yi == 0; }))
return sub3(m, x, y, w);
for (int i = 0; i < m; i++)
val[x[i] + 1][y[i] + 1] += w[i];
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
psum[x][y] += psum[x][y - 1] + val[x][y];
memset(table, -1, sizeof(table));
return dp(0, 0, 1);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
2516 KB |
Output is correct |
2 |
Correct |
28 ms |
3004 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
92 ms |
8400 KB |
Output is correct |
6 |
Correct |
85 ms |
8436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1748 KB |
Output is correct |
2 |
Correct |
49 ms |
7468 KB |
Output is correct |
3 |
Correct |
66 ms |
8932 KB |
Output is correct |
4 |
Correct |
22 ms |
2416 KB |
Output is correct |
5 |
Correct |
26 ms |
3028 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
2 ms |
1748 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
25 ms |
4736 KB |
Output is correct |
13 |
Correct |
35 ms |
5312 KB |
Output is correct |
14 |
Correct |
26 ms |
4720 KB |
Output is correct |
15 |
Correct |
36 ms |
4952 KB |
Output is correct |
16 |
Correct |
25 ms |
4748 KB |
Output is correct |
17 |
Correct |
35 ms |
4940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
36 ms |
26924 KB |
Output is correct |
3 |
Correct |
46 ms |
29872 KB |
Output is correct |
4 |
Correct |
47 ms |
30652 KB |
Output is correct |
5 |
Correct |
67 ms |
34376 KB |
Output is correct |
6 |
Correct |
59 ms |
35088 KB |
Output is correct |
7 |
Correct |
66 ms |
35140 KB |
Output is correct |
8 |
Correct |
75 ms |
35044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
212348 KB |
Output is correct |
2 |
Correct |
87 ms |
212360 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
1752 KB |
Output is correct |
8 |
Correct |
88 ms |
212348 KB |
Output is correct |
9 |
Correct |
91 ms |
213768 KB |
Output is correct |
10 |
Correct |
103 ms |
215548 KB |
Output is correct |
11 |
Correct |
93 ms |
213780 KB |
Output is correct |
12 |
Correct |
99 ms |
215500 KB |
Output is correct |
13 |
Correct |
85 ms |
212944 KB |
Output is correct |
14 |
Correct |
90 ms |
215488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
212348 KB |
Output is correct |
2 |
Correct |
87 ms |
212360 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
1752 KB |
Output is correct |
8 |
Correct |
88 ms |
212348 KB |
Output is correct |
9 |
Correct |
91 ms |
213768 KB |
Output is correct |
10 |
Correct |
103 ms |
215548 KB |
Output is correct |
11 |
Correct |
93 ms |
213780 KB |
Output is correct |
12 |
Correct |
99 ms |
215500 KB |
Output is correct |
13 |
Correct |
85 ms |
212944 KB |
Output is correct |
14 |
Correct |
90 ms |
215488 KB |
Output is correct |
15 |
Correct |
99 ms |
215464 KB |
Output is correct |
16 |
Correct |
96 ms |
212880 KB |
Output is correct |
17 |
Correct |
124 ms |
216648 KB |
Output is correct |
18 |
Correct |
105 ms |
216388 KB |
Output is correct |
19 |
Correct |
116 ms |
216868 KB |
Output is correct |
20 |
Correct |
109 ms |
216908 KB |
Output is correct |
21 |
Correct |
110 ms |
216976 KB |
Output is correct |
22 |
Correct |
116 ms |
218364 KB |
Output is correct |
23 |
Correct |
94 ms |
216396 KB |
Output is correct |
24 |
Correct |
107 ms |
216940 KB |
Output is correct |
25 |
Correct |
92 ms |
215500 KB |
Output is correct |
26 |
Correct |
92 ms |
215948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
212348 KB |
Output is correct |
2 |
Correct |
87 ms |
212360 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
1752 KB |
Output is correct |
8 |
Correct |
88 ms |
212348 KB |
Output is correct |
9 |
Correct |
91 ms |
213768 KB |
Output is correct |
10 |
Correct |
103 ms |
215548 KB |
Output is correct |
11 |
Correct |
93 ms |
213780 KB |
Output is correct |
12 |
Correct |
99 ms |
215500 KB |
Output is correct |
13 |
Correct |
85 ms |
212944 KB |
Output is correct |
14 |
Correct |
90 ms |
215488 KB |
Output is correct |
15 |
Correct |
99 ms |
215464 KB |
Output is correct |
16 |
Correct |
96 ms |
212880 KB |
Output is correct |
17 |
Correct |
124 ms |
216648 KB |
Output is correct |
18 |
Correct |
105 ms |
216388 KB |
Output is correct |
19 |
Correct |
116 ms |
216868 KB |
Output is correct |
20 |
Correct |
109 ms |
216908 KB |
Output is correct |
21 |
Correct |
110 ms |
216976 KB |
Output is correct |
22 |
Correct |
116 ms |
218364 KB |
Output is correct |
23 |
Correct |
94 ms |
216396 KB |
Output is correct |
24 |
Correct |
107 ms |
216940 KB |
Output is correct |
25 |
Correct |
92 ms |
215500 KB |
Output is correct |
26 |
Correct |
92 ms |
215948 KB |
Output is correct |
27 |
Correct |
681 ms |
296060 KB |
Output is correct |
28 |
Correct |
249 ms |
228608 KB |
Output is correct |
29 |
Correct |
781 ms |
294248 KB |
Output is correct |
30 |
Correct |
784 ms |
337000 KB |
Output is correct |
31 |
Correct |
781 ms |
337552 KB |
Output is correct |
32 |
Correct |
232 ms |
228556 KB |
Output is correct |
33 |
Correct |
810 ms |
361532 KB |
Output is correct |
34 |
Correct |
760 ms |
361640 KB |
Output is correct |
35 |
Correct |
672 ms |
301748 KB |
Output is correct |
36 |
Correct |
735 ms |
307276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
36 ms |
26924 KB |
Output is correct |
3 |
Correct |
46 ms |
29872 KB |
Output is correct |
4 |
Correct |
47 ms |
30652 KB |
Output is correct |
5 |
Correct |
67 ms |
34376 KB |
Output is correct |
6 |
Correct |
59 ms |
35088 KB |
Output is correct |
7 |
Correct |
66 ms |
35140 KB |
Output is correct |
8 |
Correct |
75 ms |
35044 KB |
Output is correct |
9 |
Runtime error |
33 ms |
5852 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
2516 KB |
Output is correct |
2 |
Correct |
28 ms |
3004 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
92 ms |
8400 KB |
Output is correct |
6 |
Correct |
85 ms |
8436 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
49 ms |
7468 KB |
Output is correct |
9 |
Correct |
66 ms |
8932 KB |
Output is correct |
10 |
Correct |
22 ms |
2416 KB |
Output is correct |
11 |
Correct |
26 ms |
3028 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
1 ms |
1748 KB |
Output is correct |
14 |
Correct |
2 ms |
1748 KB |
Output is correct |
15 |
Correct |
1 ms |
1748 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
25 ms |
4736 KB |
Output is correct |
19 |
Correct |
35 ms |
5312 KB |
Output is correct |
20 |
Correct |
26 ms |
4720 KB |
Output is correct |
21 |
Correct |
36 ms |
4952 KB |
Output is correct |
22 |
Correct |
25 ms |
4748 KB |
Output is correct |
23 |
Correct |
35 ms |
4940 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
36 ms |
26924 KB |
Output is correct |
26 |
Correct |
46 ms |
29872 KB |
Output is correct |
27 |
Correct |
47 ms |
30652 KB |
Output is correct |
28 |
Correct |
67 ms |
34376 KB |
Output is correct |
29 |
Correct |
59 ms |
35088 KB |
Output is correct |
30 |
Correct |
66 ms |
35140 KB |
Output is correct |
31 |
Correct |
75 ms |
35044 KB |
Output is correct |
32 |
Correct |
99 ms |
212348 KB |
Output is correct |
33 |
Correct |
87 ms |
212360 KB |
Output is correct |
34 |
Correct |
1 ms |
1748 KB |
Output is correct |
35 |
Correct |
1 ms |
1748 KB |
Output is correct |
36 |
Correct |
1 ms |
1748 KB |
Output is correct |
37 |
Correct |
1 ms |
1748 KB |
Output is correct |
38 |
Correct |
1 ms |
1752 KB |
Output is correct |
39 |
Correct |
88 ms |
212348 KB |
Output is correct |
40 |
Correct |
91 ms |
213768 KB |
Output is correct |
41 |
Correct |
103 ms |
215548 KB |
Output is correct |
42 |
Correct |
93 ms |
213780 KB |
Output is correct |
43 |
Correct |
99 ms |
215500 KB |
Output is correct |
44 |
Correct |
85 ms |
212944 KB |
Output is correct |
45 |
Correct |
90 ms |
215488 KB |
Output is correct |
46 |
Correct |
99 ms |
215464 KB |
Output is correct |
47 |
Correct |
96 ms |
212880 KB |
Output is correct |
48 |
Correct |
124 ms |
216648 KB |
Output is correct |
49 |
Correct |
105 ms |
216388 KB |
Output is correct |
50 |
Correct |
116 ms |
216868 KB |
Output is correct |
51 |
Correct |
109 ms |
216908 KB |
Output is correct |
52 |
Correct |
110 ms |
216976 KB |
Output is correct |
53 |
Correct |
116 ms |
218364 KB |
Output is correct |
54 |
Correct |
94 ms |
216396 KB |
Output is correct |
55 |
Correct |
107 ms |
216940 KB |
Output is correct |
56 |
Correct |
92 ms |
215500 KB |
Output is correct |
57 |
Correct |
92 ms |
215948 KB |
Output is correct |
58 |
Correct |
681 ms |
296060 KB |
Output is correct |
59 |
Correct |
249 ms |
228608 KB |
Output is correct |
60 |
Correct |
781 ms |
294248 KB |
Output is correct |
61 |
Correct |
784 ms |
337000 KB |
Output is correct |
62 |
Correct |
781 ms |
337552 KB |
Output is correct |
63 |
Correct |
232 ms |
228556 KB |
Output is correct |
64 |
Correct |
810 ms |
361532 KB |
Output is correct |
65 |
Correct |
760 ms |
361640 KB |
Output is correct |
66 |
Correct |
672 ms |
301748 KB |
Output is correct |
67 |
Correct |
735 ms |
307276 KB |
Output is correct |
68 |
Runtime error |
33 ms |
5852 KB |
Execution killed with signal 11 |
69 |
Halted |
0 ms |
0 KB |
- |