oj.uz

Submission #825278

# Submission time Handle Problem Language Result Execution time Memory
825278 2023-08-14T16:38:16 Z PixelCat Catfish Farm (IOI22_fish) C++17
52 / 100
 723 ms 221216 KB 
#include "fish.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

inline void chmax(int &x, int val) { x = max(x, val); }

const int MAXN = 3000;
const int INF = 1e15;

int n, m;
int pre[MAXN + 10][MAXN + 10];
int dp1[MAXN + 10][MAXN + 10];
int dp2[MAXN + 10][MAXN + 10];

long long max_weights(i32 N, i32 M, vector<i32> X, vector<i32> Y,
                      vector<i32> W) {
    n = N;
    m = M;

    memset(pre, 0, sizeof(pre));
    For(i, 0, m - 1) {
        X[i]++; Y[i]++;
        pre[X[i]][Y[i]] += W[i];
    }
    For(i, 1, n) For(j, 1, n) {
        pre[i][j] += pre[i][j - 1];
    }

    For(i, 0, n + 1) For(j, 0, n + 1) {
        dp1[i][j] = dp2[i][j] = -INF;
    }
    dp2[0][0] = 0;

    For(i, 1, n + 1) {
        int mx = -INF;
        For(j, 1, n) {
            chmax(mx, dp1[i - 1][j] - pre[i - 1][j]);
            chmax(mx, dp2[i - 1][j] - pre[i - 1][j]);

            dp1[i][j] = dp2[i - 1][0];
            chmax(dp1[i][j], mx);
            dp1[i][j] += pre[i - 1][j];
        }
        mx = -INF;
        Forr(j, n, 0) {
            chmax(mx, dp2[i - 1][j]);

            dp2[i][j] = dp1[i - 1][j];
            chmax(dp2[i][j], mx - pre[i - 1][j]);
            dp2[i][j] += pre[i][j];
        }
    }

    int ans = 0;
    For(j, 0, n) chmax(ans, dp2[n + 1][j]);
    return ans;
}

/*

5 4
0 2 5
1 1 2
4 4 1
3 3 3

8

*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 681 ms 149148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 71200 KB Output is correct
2 Runtime error 703 ms 153124 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 723 ms 144168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 71244 KB Output is correct
2 Correct 24 ms 71188 KB Output is correct
3 Correct 24 ms 71252 KB Output is correct
4 Correct 25 ms 71212 KB Output is correct
5 Correct 25 ms 71240 KB Output is correct
6 Correct 25 ms 71244 KB Output is correct
7 Correct 25 ms 71236 KB Output is correct
8 Correct 25 ms 71152 KB Output is correct
9 Correct 25 ms 72804 KB Output is correct
10 Correct 27 ms 75128 KB Output is correct
11 Correct 26 ms 72700 KB Output is correct
12 Correct 28 ms 74992 KB Output is correct
13 Correct 26 ms 71848 KB Output is correct
14 Correct 27 ms 75092 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 71244 KB Output is correct
2 Correct 24 ms 71188 KB Output is correct
3 Correct 24 ms 71252 KB Output is correct
4 Correct 25 ms 71212 KB Output is correct
5 Correct 25 ms 71240 KB Output is correct
6 Correct 25 ms 71244 KB Output is correct
7 Correct 25 ms 71236 KB Output is correct
8 Correct 25 ms 71152 KB Output is correct
9 Correct 25 ms 72804 KB Output is correct
10 Correct 27 ms 75128 KB Output is correct
11 Correct 26 ms 72700 KB Output is correct
12 Correct 28 ms 74992 KB Output is correct
13 Correct 26 ms 71848 KB Output is correct
14 Correct 27 ms 75092 KB Output is correct
15 Correct 28 ms 74968 KB Output is correct
16 Correct 28 ms 72020 KB Output is correct
17 Correct 36 ms 76876 KB Output is correct
18 Correct 36 ms 76876 KB Output is correct
19 Correct 37 ms 76860 KB Output is correct
20 Correct 36 ms 76816 KB Output is correct
21 Correct 37 ms 76768 KB Output is correct
22 Correct 48 ms 78504 KB Output is correct
23 Correct 29 ms 75408 KB Output is correct
24 Correct 32 ms 76160 KB Output is correct
25 Correct 26 ms 75084 KB Output is correct
26 Correct 28 ms 75348 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 71244 KB Output is correct
2 Correct 24 ms 71188 KB Output is correct
3 Correct 24 ms 71252 KB Output is correct
4 Correct 25 ms 71212 KB Output is correct
5 Correct 25 ms 71240 KB Output is correct
6 Correct 25 ms 71244 KB Output is correct
7 Correct 25 ms 71236 KB Output is correct
8 Correct 25 ms 71152 KB Output is correct
9 Correct 25 ms 72804 KB Output is correct
10 Correct 27 ms 75128 KB Output is correct
11 Correct 26 ms 72700 KB Output is correct
12 Correct 28 ms 74992 KB Output is correct
13 Correct 26 ms 71848 KB Output is correct
14 Correct 27 ms 75092 KB Output is correct
15 Correct 28 ms 74968 KB Output is correct
16 Correct 28 ms 72020 KB Output is correct
17 Correct 36 ms 76876 KB Output is correct
18 Correct 36 ms 76876 KB Output is correct
19 Correct 37 ms 76860 KB Output is correct
20 Correct 36 ms 76816 KB Output is correct
21 Correct 37 ms 76768 KB Output is correct
22 Correct 48 ms 78504 KB Output is correct
23 Correct 29 ms 75408 KB Output is correct
24 Correct 32 ms 76160 KB Output is correct
25 Correct 26 ms 75084 KB Output is correct
26 Correct 28 ms 75348 KB Output is correct
27 Correct 121 ms 212760 KB Output is correct
28 Correct 84 ms 92532 KB Output is correct
29 Correct 197 ms 221144 KB Output is correct
30 Correct 237 ms 221140 KB Output is correct
31 Correct 220 ms 221140 KB Output is correct
32 Correct 101 ms 88760 KB Output is correct
33 Correct 232 ms 221064 KB Output is correct
34 Correct 224 ms 221216 KB Output is correct
35 Correct 146 ms 216804 KB Output is correct
36 Correct 208 ms 221108 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 723 ms 144168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 681 ms 149148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -