oj.uz

Submission #1022870

# Submission time Handle Problem Language Result Execution time Memory
1022870 2024-07-14T06:47:41 Z vjudge1 Catfish Farm (IOI22_fish) C++17
0 / 100
 15 ms 4700 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 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;
        }
        dp[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++){
                dp[i][j] = 0;
                for(int k=j; k<=n; k++){
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + pref[i][k] - pref[i][j]);
                }
                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=1; 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 15 ms 4700 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 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 15 ms 4700 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
2 Halted 0 ms 0 KB -