oj.uz

Submission #994182

# Submission time Handle Problem Language Result Execution time Memory
994182 2024-06-07T08:22:47 Z cpdreamer Catfish Farm (IOI22_fish) C++17
35 / 100
 959 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define V vector
#define pb push_back
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
    vector<vector<long long >>grid(N+1,vector<long long>(N+1,0));
    for(int i=0;i<M;i++){
        grid[X[i]][Y[i]+1]+=W[i];
    }
    for(int i=0;i<N;i++){
        for(int j=1;j<=N;j++){
            grid[i][j]+=grid[i][j-1];
        }
    }
    V<V<V<ll>>>dp(N,V<V<ll>>(N+1,V<ll>(N+1,0)));
    V<V<V<ll>>>vp(N,V<V<ll>>(N+1,V<ll>(N+1,0)));
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            dp[0][i][j]=max(0LL,grid[0][j]-grid[0][i]);
            vp[0][i][j]=dp[0][i][j]+max(0LL,grid[1][i]-grid[1][j]);
        }
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<=N;j++){
            V<ll>a;
            for(int g=0;g<=N;g++)
                a.pb(dp[i-1][g][j]);
            for(int g=1;g<=N;g++)
                a[g]=max(a[g],a[g-1]);
            V<ll>b;
            for(int g=0;g<=N;g++)
                b.pb(vp[i-1][g][j]);
            for(int g=N-1;g>=0;g--)
                b[g]=max(b[g],b[g+1]);
            for(int g=0;g<=N;g++){
                if(g<=j){
                    dp[i][j][g]=b[0];
                }
                else{
                    dp[i][j][g]=max(a[g]+grid[i][g]-grid[i][j],b[g]);
                }
                vp[i][j][g]=dp[i][j][g]+max(0LL,grid[i+1][j]-grid[i+1][g]);
            }
        }
    }
    ll ans=LLONG_MIN;
    for(int i=0;i<=N;i++){
        ans=max(ans,dp[N-1][i][0]);
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 959 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 356 KB Output is correct
2 Runtime error 861 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 839 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 0 ms 348 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 0 ms 352 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 59 ms 55776 KB Output is correct
10 Correct 410 ms 432976 KB Output is correct
11 Correct 59 ms 55788 KB Output is correct
12 Correct 403 ms 433248 KB Output is correct
13 Correct 8 ms 7512 KB Output is correct
14 Correct 381 ms 432832 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 352 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 59 ms 55776 KB Output is correct
10 Correct 410 ms 432976 KB Output is correct
11 Correct 59 ms 55788 KB Output is correct
12 Correct 403 ms 433248 KB Output is correct
13 Correct 8 ms 7512 KB Output is correct
14 Correct 381 ms 432832 KB Output is correct
15 Correct 394 ms 433052 KB Output is correct
16 Correct 9 ms 7768 KB Output is correct
17 Correct 421 ms 434776 KB Output is correct
18 Correct 403 ms 434772 KB Output is correct
19 Correct 416 ms 434836 KB Output is correct
20 Correct 409 ms 434720 KB Output is correct
21 Correct 408 ms 434688 KB Output is correct
22 Correct 410 ms 436564 KB Output is correct
23 Correct 389 ms 433164 KB Output is correct
24 Correct 400 ms 434256 KB Output is correct
25 Correct 389 ms 432980 KB Output is correct
26 Correct 406 ms 433524 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 352 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 59 ms 55776 KB Output is correct
10 Correct 410 ms 432976 KB Output is correct
11 Correct 59 ms 55788 KB Output is correct
12 Correct 403 ms 433248 KB Output is correct
13 Correct 8 ms 7512 KB Output is correct
14 Correct 381 ms 432832 KB Output is correct
15 Correct 394 ms 433052 KB Output is correct
16 Correct 9 ms 7768 KB Output is correct
17 Correct 421 ms 434776 KB Output is correct
18 Correct 403 ms 434772 KB Output is correct
19 Correct 416 ms 434836 KB Output is correct
20 Correct 409 ms 434720 KB Output is correct
21 Correct 408 ms 434688 KB Output is correct
22 Correct 410 ms 436564 KB Output is correct
23 Correct 389 ms 433164 KB Output is correct
24 Correct 400 ms 434256 KB Output is correct
25 Correct 389 ms 432980 KB Output is correct
26 Correct 406 ms 433524 KB Output is correct
27 Runtime error 905 ms 2097152 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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