oj.uz

Submission #671285

# Submission time Handle Problem Language Result Execution time Memory
671285 2022-12-12T18:28:06 Z tbzard Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 216740 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

ll dp[3005][3005][3]; // A(a), (A)a, (A)
ll pref[2][3005];
int pos[3005][3005];
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    for(int i=0;i<sz(x);i++) pos[x[i]+1][y[i]+1] = w[i];
    memset(dp, -1, sizeof(dp));

    ll ans = 0;
    for(int i=1;i<=n;i++){
        memset(pref, 0, sizeof(pref));
        for(int j=1;j<=n;j++){
            pref[0][j] = pref[0][j-1] + pos[i-1][j];
            pref[1][j] = pref[1][j-1] + pos[i][j];
        }
        if(i == 1){
            for(int j=0;j<=n;j++) dp[i][j][2] = 0;
        }
        else{
            // 0
            ll mx = -1e18;
            for(int j=n;j>=0;j--){
                if(dp[i-1][j][0] != -1) mx = max(mx, dp[i-1][j][0] + pref[1][j]);
                if(dp[i-1][j][0] != -1) mx = max(mx, dp[i-1][j][2] + pref[1][j]);
                dp[i][j][0] = max(dp[i][j][0], mx - pref[1][j]);
            }

            // 1
            mx = 1e18;
            for(int j=n;j>=0;j--){
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0] + pref[1][j]);
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][2] + pref[1][j]);
            }


            // 2
            ll mx0 = -1e18, mx1 = -1e18;
            for(int j=0;j<=n;j++){
                if(dp[i-1][j][0] != -1) mx0 = max(mx0, dp[i-1][j][0]);
                if(dp[i-1][j][1] != -1) mx1 = max(mx1, dp[i-1][j][1] - pref[0][j]);
                if(dp[i-1][j][2] != -1) mx1 = max(mx1, dp[i-1][j][2] - pref[0][j]);
                dp[i][j][2] = max(dp[i][j][2], mx0);
                dp[i][j][2] = max(dp[i][j][2], mx1 + pref[0][j]);
            }
        }

        ll sum = 0;
        for(int j=0;j<=n;j++){
            sum += pos[i+1][j];
            ans = max(ans, dp[i][j][0] + sum);
            ans = max(ans, dp[i][j][2] + sum);
        }
    }

    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 214788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 212332 KB Output is correct
2 Execution timed out 1087 ms 216740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 212524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 212408 KB Output is correct
2 Correct 81 ms 212416 KB Output is correct
3 Correct 79 ms 212320 KB Output is correct
4 Correct 80 ms 212320 KB Output is correct
5 Correct 79 ms 212336 KB Output is correct
6 Correct 80 ms 212372 KB Output is correct
7 Correct 78 ms 212356 KB Output is correct
8 Incorrect 78 ms 212392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 212408 KB Output is correct
2 Correct 81 ms 212416 KB Output is correct
3 Correct 79 ms 212320 KB Output is correct
4 Correct 80 ms 212320 KB Output is correct
5 Correct 79 ms 212336 KB Output is correct
6 Correct 80 ms 212372 KB Output is correct
7 Correct 78 ms 212356 KB Output is correct
8 Incorrect 78 ms 212392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 212408 KB Output is correct
2 Correct 81 ms 212416 KB Output is correct
3 Correct 79 ms 212320 KB Output is correct
4 Correct 80 ms 212320 KB Output is correct
5 Correct 79 ms 212336 KB Output is correct
6 Correct 80 ms 212372 KB Output is correct
7 Correct 78 ms 212356 KB Output is correct
8 Incorrect 78 ms 212392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 212524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 214788 KB Time limit exceeded
2 Halted 0 ms 0 KB -