oj.uz

Submission #950822

# Submission time Handle Problem Language Result Execution time Memory
950822 2024-03-20T18:19:35 Z sysia Catfish Farm (IOI22_fish) C++17
52 / 100
 794 ms 2097152 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "fish.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef long long ll;
typedef pair<int, int> T;
const ll oo = 1e18;


void ckmax(ll &a, ll b){
    a = max(a, b);
}

ll max_weights(int n, int m, vector<int>x, vector<int>y, vector<int>w){
    vector pref(n+1, vector<ll>(n+1));
    for (int i = 0; i<m; i++){
        pref[x[i]+1][y[i]+1] = w[i];
    }
    for (int i = 1; i<=n; i++){
        for (int j = 1; j<=n; j++){
            pref[i][j] += pref[i][j-1];
        }
    }
    vector dp(n+1, vector<ll>(3, -oo));
    //dp[h][malejacy czy rosnacy][czy ita kolumna zostala ogarnieta]
    dp[0][0] = 0;
    dp[0][1] = 0;
    for (int i = 1; i<=n; i++){
        vector new_dp(n+1, vector<ll>(3, -oo));
        //h = 0
        //1) poprzednia miala dodatnie pole
        for (int h = 1; h <= n; h++){
            new_dp[0][2] = max(new_dp[0][2], max(dp[h][1], dp[h][0]) + pref[i][h]);
        }
        //2) poprzednia byla zerem
        new_dp[0][0] = max(dp[0][2], dp[0][0]);
        //h > 0
        //1) poprzednia byla pusta
        for (int h = 1; h <= n; h++){
            new_dp[h][0] = max(dp[0][2], dp[0][0] + pref[i-1][h]);
            new_dp[h][1] = max(dp[0][2], dp[0][0] + pref[i-1][h]);
        }
        //2) poprzednia cos miala miau
        ll mx = -oo;
        for (int h = 1; h <= n; h++){
            mx = max(mx, dp[h][0] - pref[i-1][h]);
            ckmax(new_dp[h][0], mx+pref[i-1][h]);
            ckmax(new_dp[h][1], mx+pref[i-1][h]);
        } 
        mx = -oo;
        for (int h = n; h >= 1; h--){
            mx = max(mx, dp[h][1] + pref[i][h]);
            ckmax(new_dp[h][1], mx - pref[i][h]);
        }
        debug(i);
        for (int h = 0; h <= n; h++){
            debug(h, new_dp[h]);
        }
        swap(dp, new_dp);
    }
    debug(dp);
    ll ans = 0;
    for (int h = 0; h <= n; h++){
        for (int rep = 0; rep < 3; rep++){
            ans = max(ans, dp[h][rep]);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 794 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 344 KB Output is correct
2 Runtime error 762 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 4 ms 1116 KB Output is correct
16 Correct 1 ms 576 KB Output is correct
17 Correct 14 ms 2908 KB Output is correct
18 Correct 13 ms 2908 KB Output is correct
19 Correct 19 ms 2752 KB Output is correct
20 Correct 14 ms 2908 KB Output is correct
21 Correct 13 ms 2908 KB Output is correct
22 Correct 23 ms 4688 KB Output is correct
23 Correct 6 ms 1472 KB Output is correct
24 Correct 10 ms 2304 KB Output is correct
25 Correct 5 ms 1116 KB Output is correct
26 Correct 6 ms 1372 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 4 ms 1116 KB Output is correct
16 Correct 1 ms 576 KB Output is correct
17 Correct 14 ms 2908 KB Output is correct
18 Correct 13 ms 2908 KB Output is correct
19 Correct 19 ms 2752 KB Output is correct
20 Correct 14 ms 2908 KB Output is correct
21 Correct 13 ms 2908 KB Output is correct
22 Correct 23 ms 4688 KB Output is correct
23 Correct 6 ms 1472 KB Output is correct
24 Correct 10 ms 2304 KB Output is correct
25 Correct 5 ms 1116 KB Output is correct
26 Correct 6 ms 1372 KB Output is correct
27 Correct 383 ms 71432 KB Output is correct
28 Correct 66 ms 13648 KB Output is correct
29 Correct 441 ms 84136 KB Output is correct
30 Correct 448 ms 84012 KB Output is correct
31 Correct 463 ms 84228 KB Output is correct
32 Correct 74 ms 14816 KB Output is correct
33 Correct 460 ms 84004 KB Output is correct
34 Correct 446 ms 83804 KB Output is correct
35 Correct 442 ms 76084 KB Output is correct
36 Correct 444 ms 83812 KB Output is correct

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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