oj.uz

Submission #892644

# Submission time Handle Problem Language Result Execution time Memory
892644 2023-12-25T16:04:20 Z Trisanu_Das Catfish Farm (IOI22_fish) C++17
67 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
  
typedef long long ll;
  
const int N=1e5+5;
const ll inf=1e18;
  
int n,m;
vector<vector<ll>> w;
vector<vector<vector<ll>>> dp;
ll suff[N];
ll val[N];
  
long long max_weights(int _n,int _m,vector<int> X,vector<int> Y,vector<int> W) {
    n=_n,m=_m;
    int mxy=0,mxx=0;
    for(auto x:X)mxx=max(mxx,x+1);
    for(auto x:Y)mxy=max(mxy,x+1);
    n=min(n,mxx+1);
    w=vector<vector<ll>>(n+5,vector<ll>(mxy+5));
    dp=vector<vector<vector<ll>>>(n+5,vector<vector<ll>>(mxy+5,vector<ll>(2)));
    for(int i=0;i<m;i++)w[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=mxy;j++)w[i][j]+=w[i][j-1];
    for(int i=1;i<=n;i++)for(int j=0;j<=mxy;j++)dp[i][j][0]=dp[i][j][1]=-inf;
    for(int i=1;i<=n;i++){
        if(i>=2)for(int j=mxy;j>=0;j--)suff[j]=max(suff[j+1],dp[i-2][j][1]);
        ll tmp=-inf,tmp2=-inf;
        for(int j=0;j<=mxy;j++){
            tmp=max(tmp,dp[i-1][j][0]-w[i][j]-w[i-1][j]);
            dp[i][j][0]=w[i-1][j]+tmp+w[i+1][j];
            if(i>=2){
                tmp2=max(tmp2,dp[i-2][j][0]-w[i-1][j]);
                dp[i][j][0]=max(dp[i][j][0],w[i-1][j]+tmp+w[i+1][j]);
                dp[i][j][0]=max(dp[i][j][0],suff[j]+w[i+1][j]);
            }
        }
        tmp=-inf;
        for(int j=mxy;j>=0;j--){
            tmp=max(tmp,dp[i-1][j][1]);
            dp[i][j][1]=tmp-w[i][j]+w[i+1][j];
            dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]);
        }
    }
    ll ans=0;
    for(int i=0;i<=mxy;i++)ans=max(ans,dp[n][i][1]);
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 46648 KB Output is correct
2 Correct 66 ms 53772 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 45 ms 49788 KB Output is correct
5 Runtime error 979 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 54132 KB Output is correct
3 Correct 95 ms 64072 KB Output is correct
4 Correct 57 ms 48032 KB Output is correct
5 Correct 65 ms 53824 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 43 ms 49604 KB Output is correct
12 Correct 64 ms 53652 KB Output is correct
13 Correct 72 ms 60096 KB Output is correct
14 Correct 62 ms 53648 KB Output is correct
15 Correct 68 ms 59552 KB Output is correct
16 Correct 64 ms 53648 KB Output is correct
17 Correct 70 ms 59580 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 47 ms 45652 KB Output is correct
3 Correct 54 ms 42836 KB Output is correct
4 Correct 49 ms 42580 KB Output is correct
5 Correct 69 ms 49672 KB Output is correct
6 Correct 67 ms 48972 KB Output is correct
7 Correct 71 ms 49752 KB Output is correct
8 Correct 68 ms 49740 KB Output is correct

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 352 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 1 ms 616 KB Output is correct
11 Correct 1 ms 612 KB Output is correct
12 Correct 1 ms 616 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 1 ms 612 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 352 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 1 ms 616 KB Output is correct
11 Correct 1 ms 612 KB Output is correct
12 Correct 1 ms 616 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 1 ms 612 KB Output is correct
15 Correct 6 ms 6244 KB Output is correct
16 Correct 1 ms 872 KB Output is correct
17 Correct 16 ms 8032 KB Output is correct
18 Correct 15 ms 8028 KB Output is correct
19 Correct 16 ms 8028 KB Output is correct
20 Correct 16 ms 8028 KB Output is correct
21 Correct 13 ms 5212 KB Output is correct
22 Correct 25 ms 9940 KB Output is correct
23 Correct 8 ms 6492 KB Output is correct
24 Correct 12 ms 7260 KB Output is correct
25 Correct 1 ms 856 KB Output is correct
26 Correct 8 ms 6544 KB Output is correct

Subtask #6
17.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 352 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 1 ms 616 KB Output is correct
11 Correct 1 ms 612 KB Output is correct
12 Correct 1 ms 616 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 1 ms 612 KB Output is correct
15 Correct 6 ms 6244 KB Output is correct
16 Correct 1 ms 872 KB Output is correct
17 Correct 16 ms 8032 KB Output is correct
18 Correct 15 ms 8028 KB Output is correct
19 Correct 16 ms 8028 KB Output is correct
20 Correct 16 ms 8028 KB Output is correct
21 Correct 13 ms 5212 KB Output is correct
22 Correct 25 ms 9940 KB Output is correct
23 Correct 8 ms 6492 KB Output is correct
24 Correct 12 ms 7260 KB Output is correct
25 Correct 1 ms 856 KB Output is correct
26 Correct 8 ms 6544 KB Output is correct
27 Correct 626 ms 566376 KB Output is correct
28 Correct 82 ms 41300 KB Output is correct
29 Correct 588 ms 484948 KB Output is correct
30 Correct 671 ms 573112 KB Output is correct
31 Correct 858 ms 573264 KB Output is correct
32 Correct 92 ms 26448 KB Output is correct
33 Correct 684 ms 573308 KB Output is correct
34 Correct 689 ms 573336 KB Output is correct
35 Correct 59 ms 33876 KB Output is correct
36 Correct 297 ms 224596 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 47 ms 45652 KB Output is correct
3 Correct 54 ms 42836 KB Output is correct
4 Correct 49 ms 42580 KB Output is correct
5 Correct 69 ms 49672 KB Output is correct
6 Correct 67 ms 48972 KB Output is correct
7 Correct 71 ms 49752 KB Output is correct
8 Correct 68 ms 49740 KB Output is correct
9 Execution timed out 1063 ms 2097152 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 46648 KB Output is correct
2 Correct 66 ms 53772 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 45 ms 49788 KB Output is correct
5 Runtime error 979 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -