oj.uz

Submission #1022933

# Submission time Handle Problem Language Result Execution time Memory
1022933 2024-07-14T07:46:06 Z vjudge1 Catfish Farm (IOI22_fish) C++17
35 / 100
 71 ms 15184 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 suf[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]);
                }
            }
        }
        //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 5972 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 2392 KB Output is correct
2 Incorrect 35 ms 9808 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 2396 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Correct 57 ms 9544 KB Output is correct
11 Correct 9 ms 7516 KB Output is correct
12 Correct 51 ms 9392 KB Output is correct
13 Correct 3 ms 3672 KB Output is correct
14 Correct 58 ms 9300 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Correct 57 ms 9544 KB Output is correct
11 Correct 9 ms 7516 KB Output is correct
12 Correct 51 ms 9392 KB Output is correct
13 Correct 3 ms 3672 KB Output is correct
14 Correct 58 ms 9300 KB Output is correct
15 Correct 68 ms 9464 KB Output is correct
16 Correct 2 ms 3676 KB Output is correct
17 Correct 61 ms 11356 KB Output is correct
18 Correct 61 ms 11092 KB Output is correct
19 Correct 60 ms 11604 KB Output is correct
20 Correct 62 ms 13580 KB Output is correct
21 Correct 61 ms 13396 KB Output is correct
22 Correct 71 ms 15184 KB Output is correct
23 Correct 54 ms 12368 KB Output is correct
24 Correct 58 ms 13396 KB Output is correct
25 Correct 51 ms 11344 KB Output is correct
26 Correct 56 ms 12112 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Correct 57 ms 9544 KB Output is correct
11 Correct 9 ms 7516 KB Output is correct
12 Correct 51 ms 9392 KB Output is correct
13 Correct 3 ms 3672 KB Output is correct
14 Correct 58 ms 9300 KB Output is correct
15 Correct 68 ms 9464 KB Output is correct
16 Correct 2 ms 3676 KB Output is correct
17 Correct 61 ms 11356 KB Output is correct
18 Correct 61 ms 11092 KB Output is correct
19 Correct 60 ms 11604 KB Output is correct
20 Correct 62 ms 13580 KB Output is correct
21 Correct 61 ms 13396 KB Output is correct
22 Correct 71 ms 15184 KB Output is correct
23 Correct 54 ms 12368 KB Output is correct
24 Correct 58 ms 13396 KB Output is correct
25 Correct 51 ms 11344 KB Output is correct
26 Correct 56 ms 12112 KB Output is correct
27 Incorrect 1 ms 4444 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 2396 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 5972 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
2 Halted 0 ms 0 KB -