oj.uz

Submission #1067621

# Submission time Handle Problem Language Result Execution time Memory
1067621 2024-08-20T21:46:56 Z HorizonWest Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
#include <bits/stdc++.h>
//#include "fish.h"
using namespace std;

#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) 
{
    //vector <vector<pair<int, int>>> v(n + 1, vector <pair<int, int>> ());

    vector <vector<ll>> v(n, vector <ll> (n+1, 0)); 
    map <int, map <int, int>> mp; 

    for(int i = 0; i < m; i++){
        v[X[i]][Y[i]+1] = W[i];
        //v[X[i]].push_back({ Y[i], W[i] });
    }

    vector <vector<ll>> dp1(n + 1, vector <ll> (n + 1, 0)), 
        dp2(n + 1, vector <ll> (n + 1, 0));

    ll ans = 0; 

    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= n; j++){
            v[i][j] += v[i][j-1];
        }
    }

    auto C = [&] (int i, int j, int k) -> ll
    {
        ll ans = 0;
        if(i >= 0 && i < n) {
            ans = ans + max(0LL, v[i][j] - v[i][k]);
        }
        return ans;
    };

    for(int i = 0; i < n; i++)
    {   
        for(int j = 0; j <= n; j++)
        {
            for(int k = 0; k <= n; k++){
                dp1[i][j] = max(dp1[i][j], (i > 1 ? dp2[i-2][k] : 0LL) + C(i-1, j, k) + C(i+1, j, 0));
            }

            for(int k = 0; k <= n; k++){    
                dp1[i][j] = max(dp1[i][j], (i != 0 ? dp1[i-1][k] : 0) + C(i-1, j, k) + C(i+1, j, 0) - C(i, k, 0));
            }

            for(int k = 0; k <= n; k++){
                dp2[i][j] = max(dp2[i][j], (i != 0 ? dp1[i-1][k] : 0) - C(i, j, 0) + C(i+1, j, 0));
                dp2[i][j] = max(dp2[i][j], (i != 0 ? dp2[i-1][k] : 0) - C(i, j, 0) + C(i+1, j, 0));
            }

            ans = max(ans, max(dp1[i][j], dp2[i][j])); 
        }
    }

    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 921 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 348 KB Output is correct
2 Runtime error 833 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 783 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 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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 20 ms 860 KB Output is correct
10 Correct 153 ms 2664 KB Output is correct
11 Correct 20 ms 860 KB Output is correct
12 Correct 158 ms 2624 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 162 ms 2396 KB Output is correct

Subtask #5
21.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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 20 ms 860 KB Output is correct
10 Correct 153 ms 2664 KB Output is correct
11 Correct 20 ms 860 KB Output is correct
12 Correct 158 ms 2624 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 162 ms 2396 KB Output is correct
15 Correct 155 ms 2580 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Correct 164 ms 4420 KB Output is correct
18 Correct 162 ms 4572 KB Output is correct
19 Correct 172 ms 4184 KB Output is correct
20 Correct 163 ms 4284 KB Output is correct
21 Correct 162 ms 4184 KB Output is correct
22 Correct 173 ms 5964 KB Output is correct
23 Correct 157 ms 2908 KB Output is correct
24 Correct 160 ms 3676 KB Output is correct
25 Correct 160 ms 2392 KB Output is correct
26 Correct 159 ms 2904 KB Output is correct

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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 20 ms 860 KB Output is correct
10 Correct 153 ms 2664 KB Output is correct
11 Correct 20 ms 860 KB Output is correct
12 Correct 158 ms 2624 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 162 ms 2396 KB Output is correct
15 Correct 155 ms 2580 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Correct 164 ms 4420 KB Output is correct
18 Correct 162 ms 4572 KB Output is correct
19 Correct 172 ms 4184 KB Output is correct
20 Correct 163 ms 4284 KB Output is correct
21 Correct 162 ms 4184 KB Output is correct
22 Correct 173 ms 5964 KB Output is correct
23 Correct 157 ms 2908 KB Output is correct
24 Correct 160 ms 3676 KB Output is correct
25 Correct 160 ms 2392 KB Output is correct
26 Correct 159 ms 2904 KB Output is correct
27 Execution timed out 1069 ms 212052 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 783 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 921 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -