oj.uz

Submission #625704

# Submission time Handle Problem Language Result Execution time Memory
625704 2022-08-10T17:22:10 Z Clan328 Catfish Farm (IOI22_fish) C++17
9 / 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()
#define int long long

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;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

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;
}

void settings() {
    #ifdef LOCAL
        freopen("io/input.txt", "r", stdin);
        freopen("io/output.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(0);
    cin.tie(0);
}

long long max_weights(signed N, signed M, std::vector<signed> X, std::vector<signed> Y,
                      std::vector<signed> W) {
    int NY = Y[0];
    for (int i = 1; i < M; i++) {
        NY = max(NY, (ll)Y[i]);
    }
    NY++;

    vvi a(N, vi(NY)), sum(N, vi(NY+1));
    for (int i = 0; i < M; i++) {
        a[X[i]][Y[i]] = W[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= NY; j++) sum[i][j] = sum[i][j-1]+a[i][j-1];
    }

    vvi dp(N, vi(NY+1)), aux(N, vi(NY+1));
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < NY+1; j++) {
            for (int k = 0; k < NY+1; k++) {
                if (j <= k) {
                    int tmp = dp[i-1][k] + sum[i][k]-sum[i][j];
                    if (dp[i][j] < tmp) {
                        dp[i][j] = tmp;
                        aux[i][j] = sum[i][k]-sum[i][j];
                    }
                } else {
                    int tmp = dp[i-1][k] + max(0LL, sum[i-1][j]-sum[i-1][k]-aux[i-1][k]);
                    if (dp[i][j] <= tmp) {
                        dp[i][j] = tmp;
                        aux[i][j] = 0;
                    }
                }

                if (i-2 < 0) continue;
                int tmp = dp[i-2][k] + max(sum[i-1][k], sum[i-1][j]);
                if (dp[i][j] <= tmp) {
                    dp[i][j] = tmp;
                    aux[i][j] = 0;
                }

                // if (i-3 < 0) continue;
                // tmp = dp[i-3][k] + sum[i-2][k] + sum[i-1][j];
                // if (dp[i][j] <= tmp) {
                //     dp[i][j] = tmp;
                //     aux[i][j] = 0;
                // }
            }
        }
    }

    // for (int i = 0; i <N; i++) cout << a[i] << nL;
    // for (int i = 0; i <N; i++) cout << dp[i] << nL;

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

  return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 895 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 1 ms 212 KB Output is correct
2 Execution timed out 1041 ms 2097152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 22228 KB Output is correct
2 Correct 31 ms 22212 KB Output is correct
3 Correct 58 ms 21968 KB Output is correct
4 Correct 60 ms 23424 KB Output is correct
5 Correct 61 ms 24752 KB Output is correct
6 Correct 62 ms 25328 KB Output is correct
7 Correct 69 ms 25388 KB Output is correct
8 Correct 62 ms 25376 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '447839680917'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '447839680917'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '447839680917'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 22228 KB Output is correct
2 Correct 31 ms 22212 KB Output is correct
3 Correct 58 ms 21968 KB Output is correct
4 Correct 60 ms 23424 KB Output is correct
5 Correct 61 ms 24752 KB Output is correct
6 Correct 62 ms 25328 KB Output is correct
7 Correct 69 ms 25388 KB Output is correct
8 Correct 62 ms 25376 KB Output is correct
9 Runtime error 912 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 895 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -