oj.uz

Submission #834302

# Submission time Handle Problem Language Result Execution time Memory
834302 2023-08-22T12:47:19 Z gagik_2007 Catfish Farm (IOI22_fish) C++17
35 / 100
 409 ms 439504 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=307;
ll n,m,k;
ll pf[N][N];
ll dp[N][N][N];
ll dh[N][N][N];

ll max_weights(int NN, int MM, vector<int> X, vector<int> Y, vector<int> W) {
    n=NN;
    m=MM;
    for(int i=0;i<m;i++){
        pf[X[i]][Y[i]+1]=W[i];
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=n;j++){
            pf[i][j]+=pf[i][j-1];
        }
    }
    for(int i=0;i<=n;i++){
        dp[0][0][i]=pf[1][i];
        // cout<<"0, 0, "<<i<<": "<<dp[0][0][i]<<endl;
    }
    // cout<<endl;
    ll ans=0;
    for(int i=1;i<n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                ll res=0;
                res-=pf[i][min(k,j)];
                if(i!=n-1){
                    res+=pf[i+1][j];
                }
                // cout<<i<<", "<<k<<", "<<j<<": ";
                ll mres=res;
                if(j<=k)mres+=dp[i-1][0][k];
                else{
                    mres+=max(dp[i-1][j][k],dh[i-1][j-1][k]+pf[i-1][j]);
                }
                dp[i][k][j]=max(dp[i][k][j],mres);

                ans=max(ans,dp[i][k][j]);

                dh[i][k][j]=dp[i][k][j]-pf[i][max(j,k)];
                // cout<<dp[i][k][j]<<"\n";

                if(k!=0)dh[i][k][j]=max(dh[i][k][j],dh[i][k-1][j]);
            }
            for(int k=n-1;k>=0;k--){
                dp[i][k][j]=max(dp[i][k][j],dp[i][k+1][j]);
            }
            // cout<<endl;
        }
        // cout<<endl;
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 5688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 55 ms 9660 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 76 ms 109820 KB Output is correct
10 Correct 409 ms 435968 KB Output is correct
11 Correct 72 ms 109772 KB Output is correct
12 Correct 380 ms 435976 KB Output is correct
13 Correct 17 ms 27920 KB Output is correct
14 Correct 362 ms 435964 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 76 ms 109820 KB Output is correct
10 Correct 409 ms 435968 KB Output is correct
11 Correct 72 ms 109772 KB Output is correct
12 Correct 380 ms 435976 KB Output is correct
13 Correct 17 ms 27920 KB Output is correct
14 Correct 362 ms 435964 KB Output is correct
15 Correct 362 ms 435908 KB Output is correct
16 Correct 18 ms 27988 KB Output is correct
17 Correct 363 ms 437716 KB Output is correct
18 Correct 360 ms 437716 KB Output is correct
19 Correct 367 ms 437708 KB Output is correct
20 Correct 370 ms 437676 KB Output is correct
21 Correct 384 ms 437676 KB Output is correct
22 Correct 374 ms 439504 KB Output is correct
23 Correct 372 ms 436268 KB Output is correct
24 Correct 368 ms 437076 KB Output is correct
25 Correct 359 ms 435904 KB Output is correct
26 Correct 369 ms 436172 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 76 ms 109820 KB Output is correct
10 Correct 409 ms 435968 KB Output is correct
11 Correct 72 ms 109772 KB Output is correct
12 Correct 380 ms 435976 KB Output is correct
13 Correct 17 ms 27920 KB Output is correct
14 Correct 362 ms 435964 KB Output is correct
15 Correct 362 ms 435908 KB Output is correct
16 Correct 18 ms 27988 KB Output is correct
17 Correct 363 ms 437716 KB Output is correct
18 Correct 360 ms 437716 KB Output is correct
19 Correct 367 ms 437708 KB Output is correct
20 Correct 370 ms 437676 KB Output is correct
21 Correct 384 ms 437676 KB Output is correct
22 Correct 374 ms 439504 KB Output is correct
23 Correct 372 ms 436268 KB Output is correct
24 Correct 368 ms 437076 KB Output is correct
25 Correct 359 ms 435904 KB Output is correct
26 Correct 369 ms 436172 KB Output is correct
27 Runtime error 7 ms 580 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 5688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -