oj.uz

Submission #993521

# Submission time Handle Problem Language Result Execution time Memory
993521 2024-06-05T23:06:32 Z Clan328 Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 2097152 KB 
#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
    for (auto elem : v) 
        stream << elem << " ";
    return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
        stream >> elem;
   return stream;
}

long long max_weights(int N, int M, vi X, vi Y,
                      vi W) {
    ll maxY = 0;
    for (int i = 0; i < M; i++) maxY = max(maxY, (ll)Y[i]);
    maxY++;
    vvl mat(N, vl(maxY+1));
    for (int i = 0; i < M; i++) mat[X[i]][Y[i]] = W[i];

    vector<vvl> dp(N, vvl(maxY+1, vl(maxY+1)));
    
    ll _tmp1 = 0;
    for (int j = 0; j <= maxY; j++) {
        if (j > 0) _tmp1 += mat[0][j-1];

        ll _tmp2 = 0;
        for (int k = 0; k <= maxY; k++) {
            if (k <= j) {
                if (k > 0) _tmp2 -= mat[0][k-1];
            } else {
                if (k > 0) _tmp2 += mat[1][k-1];
            }

            dp[1][j][k] = _tmp1+_tmp2;
            // cout << j << " " << k << " " << _tmp1+_tmp2 << nL;
        }
    }
    
    for (int i = 2; i < N; i++) {
        ll tmp1 = 0;
        for (int j = 0; j <= maxY; j++) {
            if (j > 0) tmp1 += mat[i-1][j-1];

            ll tmp2 = 0;
            for (int k = 0; k <= maxY; k++) {
                if (k <= j) {
                    if (k > 0) tmp2 -= mat[i-1][k-1];
                } else {
                    if (k > 0) tmp2 += mat[i][k-1];
                }

                ll tmp3 = 0;
                for (int l = 0; l <= maxY;l++) {
                    if (l > k && l <= j) {
                        if (l > 0) tmp3 -= mat[i-1][l-1];
                    }

                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+tmp1+tmp2+tmp3);
                }
            }
        }
    }

    long long res = 0;
    for (int i = 0; i <= maxY; i++) {
        for (int j = 0; j <= maxY; j++)
            res = max(res, dp[N-1][i][j]);
    }

    return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 799 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Runtime error 840 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20572 KB Output is correct
2 Correct 22 ms 20580 KB Output is correct
3 Correct 29 ms 19984 KB Output is correct
4 Correct 27 ms 21596 KB Output is correct
5 Correct 38 ms 22868 KB Output is correct
6 Correct 35 ms 23116 KB Output is correct
7 Correct 44 ms 23120 KB Output is correct
8 Correct 38 ms 23124 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Execution timed out 1073 ms 216672 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Execution timed out 1073 ms 216672 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20572 KB Output is correct
2 Correct 22 ms 20580 KB Output is correct
3 Correct 29 ms 19984 KB Output is correct
4 Correct 27 ms 21596 KB Output is correct
5 Correct 38 ms 22868 KB Output is correct
6 Correct 35 ms 23116 KB Output is correct
7 Correct 44 ms 23120 KB Output is correct
8 Correct 38 ms 23124 KB Output is correct
9 Runtime error 795 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 799 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -