oj.uz

Submission #748214

# Submission time Handle Problem Language Result Execution time Memory
748214 2023-05-25T16:16:13 Z inventiontime Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 155988 KB 
#include "fish.h"

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

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

typedef long long ll;
typedef vector<int> vi;

const ll inf = 1e17;
const ll maxn = 3005;

ll fish[maxn][maxn];
ll pref[maxn][maxn];
ll dpi[maxn][maxn];
ll dpd[maxn][maxn];

ll max_weights(int n, int m, vi x, vi y, vi w) {

    loop(i, m) {
        x[i]++; y[i]++;
        fish[x[i]][y[i]] = w[i];
    }

    loop1(i, n) loop1(j, n)
        pref[i][j] = pref[i][j-1] + fish[i][j];

    loop(i, n+2) dpi[0][i] = -inf;
    loop(i, n+2) dpd[0][i] = -inf;
    dpd[0][0] = 0;

    loop1(i, n+1) {
        loop1(j, n) {
            if(i >= 2) {
                loop(k, n+1)
                    ckmax(dpi[i][j], max(dpd[i-2][k], dpi[i-2][k]) + pref[i-1][max(j, k)] - pref[i-1][0]);
            }
            loop1(k, n) if(k <= j)
                ckmax(dpi[i][j], dpi[i-1][k] + pref[i-1][j] - pref[i-1][k]);
        }
        loop(j, n+1) {
            ckmax(dpd[i][j], dpi[i-1][n] + pref[i][n] - pref[i][j]);
            loop(k, n+1) if(k >= j)
                ckmax(dpd[i][j], dpd[i-1][k] + pref[i][k] - pref[i][j]);
        }
    }

    return dpd[n+1][0];

}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 824 ms 150484 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 1 ms 340 KB Output is correct
2 Runtime error 853 ms 155988 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 911 ms 143856 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 1 ms 340 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 19 ms 3176 KB Output is correct
10 Correct 133 ms 7372 KB Output is correct
11 Correct 19 ms 3292 KB Output is correct
12 Correct 134 ms 7220 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 137 ms 7244 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 19 ms 3176 KB Output is correct
10 Correct 133 ms 7372 KB Output is correct
11 Correct 19 ms 3292 KB Output is correct
12 Correct 134 ms 7220 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 137 ms 7244 KB Output is correct
15 Correct 133 ms 7260 KB Output is correct
16 Correct 4 ms 1512 KB Output is correct
17 Correct 151 ms 9092 KB Output is correct
18 Correct 145 ms 8888 KB Output is correct
19 Correct 146 ms 9400 KB Output is correct
20 Correct 144 ms 9364 KB Output is correct
21 Correct 145 ms 9504 KB Output is correct
22 Correct 159 ms 11600 KB Output is correct
23 Correct 135 ms 8268 KB Output is correct
24 Correct 142 ms 9180 KB Output is correct
25 Correct 132 ms 7244 KB Output is correct
26 Correct 140 ms 7856 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 19 ms 3176 KB Output is correct
10 Correct 133 ms 7372 KB Output is correct
11 Correct 19 ms 3292 KB Output is correct
12 Correct 134 ms 7220 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 137 ms 7244 KB Output is correct
15 Correct 133 ms 7260 KB Output is correct
16 Correct 4 ms 1512 KB Output is correct
17 Correct 151 ms 9092 KB Output is correct
18 Correct 145 ms 8888 KB Output is correct
19 Correct 146 ms 9400 KB Output is correct
20 Correct 144 ms 9364 KB Output is correct
21 Correct 145 ms 9504 KB Output is correct
22 Correct 159 ms 11600 KB Output is correct
23 Correct 135 ms 8268 KB Output is correct
24 Correct 142 ms 9180 KB Output is correct
25 Correct 132 ms 7244 KB Output is correct
26 Correct 140 ms 7856 KB Output is correct
27 Execution timed out 1070 ms 84272 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 911 ms 143856 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 824 ms 150484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -