답안 #707362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707362	2023-03-08T22:15:23 Z	Johann	메기 농장 (IOI22_fish)	C++17	52 / 100	1000 ms	2097152 KB

fish

#include "fish.h"

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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 3e5 * 1e9 + 100;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
  vvi grid(N + 4, vi(N, 0)); // becomes prefix grid

  for (int i = 0; i < M; ++i)
    grid[X[i] + 3][Y[i]] = W[i];

  for (int x = 0; x < sz(grid); ++x)
    for (int y = 1; y < sz(grid[0]); ++y)
      grid[x][y] += grid[x][y - 1];

  vvi dpg(sz(grid), vi(sz(grid[0]), 0)); // growth stack thing
  vvi dp(sz(grid), vi(sz(grid[0]), 0));  // normal all dp
  vi dpm(sz(grid), 0);                   // maximum einer Spaltes
  for (int x = 3; x < sz(grid) - 1; ++x) // so i choose the borders
  {
    ll c1 = -INF, c2 = -INF; // running variables for case 1 and 2 // TODO: INIT
    for (int y = 0; y < sz(grid[0]); ++y)
    {
      // Case 1 - last tower in x-1 and smaller y
      c1 = max(c1, dpg[x - 1][y] - grid[x - 1][y] - grid[x][y]);
      dpg[x][y] = max(dpg[x][y], grid[x - 1][y] + grid[x + 1][y] + c1);

      // Case 2 - last tower in x-2 and smaller y
      c2 = max(c2, dp[x - 2][y] - grid[x - 1][y]);
      dpg[x][y] = max(dpg[x][y], grid[x - 1][y] + grid[x + 1][y] + c2);

      // Case 3 - last tower in x-1 and larger y (or if it is smaller, case 1 performs better)
      // here the last tower might be larger than the current one
      dp[x][y] = max(dp[x][y], dpm[x - 1] - grid[x][y] + grid[x + 1][y]);

      // Case 4 - Last Tower in x-2 and larger y (or if it is smaller, case 2 performs better)
      dpg[x][y] = max(dpg[x][y], dpm[x - 2] + grid[x + 1][y]);

      // Case 5 - Last Tower in x-3
      dpg[x][y] = max(dpg[x][y], dpm[x - 3] + grid[x - 1][y] + grid[x + 1][y]);
      // keep track for dpg & dpm
      dp[x][y] = max(dp[x][y], dpg[x][y]);
      dpm[x] = max(dpm[x], dp[x][y]);
    }
  }

  return *max_element(all(dpm));
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1144 ms	1870468 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	1040 ms	2097152 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	828 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	224 KB	Output is correct
6	Correct	1 ms	216 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	2 ms	852 KB	Output is correct
10	Correct	3 ms	2516 KB	Output is correct
11	Correct	1 ms	824 KB	Output is correct
12	Correct	2 ms	2492 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	2488 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	224 KB	Output is correct
6	Correct	1 ms	216 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	2 ms	852 KB	Output is correct
10	Correct	3 ms	2516 KB	Output is correct
11	Correct	1 ms	824 KB	Output is correct
12	Correct	2 ms	2492 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	2488 KB	Output is correct
15	Correct	3 ms	2388 KB	Output is correct
16	Correct	1 ms	440 KB	Output is correct
17	Correct	15 ms	4300 KB	Output is correct
18	Correct	15 ms	4284 KB	Output is correct
19	Correct	16 ms	4276 KB	Output is correct
20	Correct	14 ms	4284 KB	Output is correct
21	Correct	14 ms	4180 KB	Output is correct
22	Correct	26 ms	6092 KB	Output is correct
23	Correct	6 ms	2772 KB	Output is correct
24	Correct	12 ms	3580 KB	Output is correct
25	Correct	3 ms	2516 KB	Output is correct
26	Correct	5 ms	2772 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	224 KB	Output is correct
6	Correct	1 ms	216 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	2 ms	852 KB	Output is correct
10	Correct	3 ms	2516 KB	Output is correct
11	Correct	1 ms	824 KB	Output is correct
12	Correct	2 ms	2492 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	2488 KB	Output is correct
15	Correct	3 ms	2388 KB	Output is correct
16	Correct	1 ms	440 KB	Output is correct
17	Correct	15 ms	4300 KB	Output is correct
18	Correct	15 ms	4284 KB	Output is correct
19	Correct	16 ms	4276 KB	Output is correct
20	Correct	14 ms	4284 KB	Output is correct
21	Correct	14 ms	4180 KB	Output is correct
22	Correct	26 ms	6092 KB	Output is correct
23	Correct	6 ms	2772 KB	Output is correct
24	Correct	12 ms	3580 KB	Output is correct
25	Correct	3 ms	2516 KB	Output is correct
26	Correct	5 ms	2772 KB	Output is correct
27	Correct	178 ms	212420 KB	Output is correct
28	Correct	70 ms	22476 KB	Output is correct
29	Correct	258 ms	224872 KB	Output is correct
30	Correct	248 ms	224996 KB	Output is correct
31	Correct	258 ms	224848 KB	Output is correct
32	Correct	92 ms	19548 KB	Output is correct
33	Correct	257 ms	224848 KB	Output is correct
34	Correct	247 ms	224864 KB	Output is correct
35	Correct	202 ms	217088 KB	Output is correct
36	Correct	249 ms	224904 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	828 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1144 ms	1870468 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

답안 #707362

Compilation message