oj.uz

Submission #1022913

# Submission time Handle Problem Language Result Execution time Memory
1022913 2024-07-14T07:30:37 Z vjudge1 Catfish Farm (IOI22_fish) C++17
35 / 100
 94 ms 22356 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 300100;
int n, w[MAXN], m;
pii a[MAXN];

namespace A{
    ll solve(){
        ll ans = 0;
        for(int i=1; i<=m; i++){
            ans += w[i];
        }
        return ans;
    }
}

namespace B{
    ll d[3001][3001];
    ll dp[3001][3001];
    ll pref[3001][3001];
    ll ddp[3001][3001];
    ll solve(){
        for(int i=1; i<=m; i++){
            d[a[i].ff][a[i].ss] += w[i];
        }
        for(int i=1; i<=n; i++){
            dp[0][i] = -1e18;
            ddp[0][i] = -1e18;
        }
        dp[0][0] = 0;
        ddp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                pref[i][j] = pref[i][j - 1] + d[i][j];
            }
            for(int j=0; j<=n; j++){
                ddp[i][j] = 0;
                dp[i][j] = 0;
                for(int k=0; k<=j; k++){
                    ddp[i][j] = max(ddp[i][j], ddp[i-1][k] + pref[i-1][j]-pref[i-1][k]);
                }
                for(int k=0; k<=n; k++){
                    ddp[i][j] = max(ddp[i][j], dp[i-1][k]);
                }
                dp[i][j] = ddp[i][j];
                for(int k=j; k<=n; k++){
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + pref[i][k] - pref[i][j]);
                }
                for(int k=0; k<=j; k++){
                    dp[i][j] = max(dp[i][j], ddp[i-1][k] + pref[i-1][j] - pref[i-1][k]);
                }
                if(i < 2) continue;
                for(int k=0; k<=n; k++){
                    dp[i][j] = max(dp[i][j], dp[i-2][k] + pref[i-1][max(k, j)]);
                }
            }
        }
        //for(int i=1; i<=n; i++){
        //    for(int j=0; j<=n; j++){
        //        cout<<dp[i][j]<<' ';
        //    }
        //    cout<<'\n';
        //}
        ll ans = 0;
        for(int i=0; i<=n; i++) ans = max(ans, dp[n][i]);
        return ans;
    }
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y,
                      vector<int> W) {
    n = N;
    m = M;
    for(int i=1; i<=m; i++){
        a[i] = {X[i-1]+1, Y[i-1]+1};
    }
    for(int i=1; i<=m; i++){
        w[i] = W[i-1];
    }
    int ok1 = 1;
    for(int i=1; i<=m; i++){
        ok1 &= (a[i].ff % 2 == 0);
    }
    if(ok1) return A::solve();
    if(n <= 300) return B::solve();
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 7760 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Incorrect 32 ms 11048 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10704 KB Output is correct
6 Correct 1 ms 10696 KB Output is correct
7 Correct 1 ms 10688 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 18 ms 13092 KB Output is correct
10 Correct 82 ms 20468 KB Output is correct
11 Correct 12 ms 16476 KB Output is correct
12 Correct 81 ms 16860 KB Output is correct
13 Correct 3 ms 13264 KB Output is correct
14 Correct 77 ms 18512 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10704 KB Output is correct
6 Correct 1 ms 10696 KB Output is correct
7 Correct 1 ms 10688 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 18 ms 13092 KB Output is correct
10 Correct 82 ms 20468 KB Output is correct
11 Correct 12 ms 16476 KB Output is correct
12 Correct 81 ms 16860 KB Output is correct
13 Correct 3 ms 13264 KB Output is correct
14 Correct 77 ms 18512 KB Output is correct
15 Correct 77 ms 20404 KB Output is correct
16 Correct 3 ms 13148 KB Output is correct
17 Correct 85 ms 18356 KB Output is correct
18 Correct 87 ms 20152 KB Output is correct
19 Correct 86 ms 20192 KB Output is correct
20 Correct 85 ms 22356 KB Output is correct
21 Correct 86 ms 22356 KB Output is correct
22 Correct 94 ms 22096 KB Output is correct
23 Correct 77 ms 18772 KB Output is correct
24 Correct 87 ms 19648 KB Output is correct
25 Correct 77 ms 18372 KB Output is correct
26 Correct 79 ms 16928 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10704 KB Output is correct
6 Correct 1 ms 10696 KB Output is correct
7 Correct 1 ms 10688 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 18 ms 13092 KB Output is correct
10 Correct 82 ms 20468 KB Output is correct
11 Correct 12 ms 16476 KB Output is correct
12 Correct 81 ms 16860 KB Output is correct
13 Correct 3 ms 13264 KB Output is correct
14 Correct 77 ms 18512 KB Output is correct
15 Correct 77 ms 20404 KB Output is correct
16 Correct 3 ms 13148 KB Output is correct
17 Correct 85 ms 18356 KB Output is correct
18 Correct 87 ms 20152 KB Output is correct
19 Correct 86 ms 20192 KB Output is correct
20 Correct 85 ms 22356 KB Output is correct
21 Correct 86 ms 22356 KB Output is correct
22 Correct 94 ms 22096 KB Output is correct
23 Correct 77 ms 18772 KB Output is correct
24 Correct 87 ms 19648 KB Output is correct
25 Correct 77 ms 18372 KB Output is correct
26 Correct 79 ms 16928 KB Output is correct
27 Incorrect 2 ms 4440 KB 1st lines differ - on the 1st token, expected: '2999', found: '0'
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 7760 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
2 Halted 0 ms 0 KB -