oj.uz

Submission #1075671

# Submission time Handle Problem Language Result Execution time Memory
1075671 2024-08-26T08:30:09 Z Sir_Ahmed_Imran Catfish Farm (IOI22_fish) C++17
35 / 100
 85 ms 12320 KB 
                            ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define append push_back
#define add insert
#define nl '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define terminator main
#define N 301
int n;
ll hs[N][N];
ll dp[N][N];
ll dp2[N][N];
ll dps(){
    for(int i=1;i<=n;i++)
        dp[0][i]=dp2[0][i]=-1e17;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(j<k){
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+hs[i][k]-hs[i][j]);
                    dp2[i][k]=max(dp2[i][k],dp[i-1][k]+hs[i][k]-hs[i][j]);
                }
                else{
                    dp[i][j]=max(dp[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]);
                    dp2[i][j]=max(dp2[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]);
                }
            }
            dp2[i][j]=max(dp2[i][j],dp[i-1][j]+hs[i][j]);
        }
    }
    ll ans=0;
    for(int i=0;i<=n;i++)
        ans=max(ans,max(dp[n][i],dp2[n][i]));
    return ans;
}
ll xs(){
    ll ans=0;
    for(int i=0;i<=n;i++)
        ans=max(ans,hs[1][i]+hs[2][n]-hs[2][i]);
    return ans;
}
ll ys(){
    for(int i=1;i<2;i++)
        dp[0][i]=dp2[0][i]=-1e17;
    for(int i=1;i<=n;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                if(j<k){
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+hs[i][k]-hs[i][j]);
                    dp2[i][k]=max(dp2[i][k],dp[i-1][k]+hs[i][k]-hs[i][j]);
                }
                else{
                    dp[i][j]=max(dp[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]);
                    dp2[i][j]=max(dp2[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]);
                }
            }
            dp2[i][j]=max(dp2[i][j],dp[i-1][j]+hs[i][j]);
        }
    }
    ll ans=0;
    for(int i=0;i<2;i++)
        ans=max(ans,max(dp[n][i],dp2[n][i]));
    return ans;
}
ll max_weights(int M,int m,vector<int> x,vector<int> y,vector<int> w){
    n=M;
    for(int i=0;i<m;i++)
        hs[x[i]+1][y[i]+1]+=w[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<n;j++)
            hs[i][j+1]+=hs[i][j];
    if(n<N) return dps();
    int mx,my;
    ll o=0;
    for(int i=mx=my=0;i<m;i++){
        mx=max(mx,x[i]);
        my=max(my,y[i]);
        o+=w[i];
    }
    if(mx<2) return xs();
    if(my<1) return ys();
    return o;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 7260 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 1 ms 348 KB Output is correct
2 Runtime error 57 ms 12320 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 3 ms 1884 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 760 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 11 ms 1372 KB Output is correct
10 Correct 61 ms 2632 KB Output is correct
11 Correct 10 ms 1372 KB Output is correct
12 Correct 72 ms 2392 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 61 ms 2384 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 760 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 11 ms 1372 KB Output is correct
10 Correct 61 ms 2632 KB Output is correct
11 Correct 10 ms 1372 KB Output is correct
12 Correct 72 ms 2392 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 61 ms 2384 KB Output is correct
15 Correct 63 ms 2476 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 74 ms 4372 KB Output is correct
18 Correct 85 ms 4140 KB Output is correct
19 Correct 70 ms 4180 KB Output is correct
20 Correct 83 ms 4108 KB Output is correct
21 Correct 77 ms 4272 KB Output is correct
22 Correct 74 ms 5972 KB Output is correct
23 Correct 68 ms 2732 KB Output is correct
24 Correct 67 ms 3660 KB Output is correct
25 Correct 58 ms 2364 KB Output is correct
26 Correct 66 ms 2644 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 760 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 11 ms 1372 KB Output is correct
10 Correct 61 ms 2632 KB Output is correct
11 Correct 10 ms 1372 KB Output is correct
12 Correct 72 ms 2392 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 61 ms 2384 KB Output is correct
15 Correct 63 ms 2476 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 74 ms 4372 KB Output is correct
18 Correct 85 ms 4140 KB Output is correct
19 Correct 70 ms 4180 KB Output is correct
20 Correct 83 ms 4108 KB Output is correct
21 Correct 77 ms 4272 KB Output is correct
22 Correct 74 ms 5972 KB Output is correct
23 Correct 68 ms 2732 KB Output is correct
24 Correct 67 ms 3660 KB Output is correct
25 Correct 58 ms 2364 KB Output is correct
26 Correct 66 ms 2644 KB Output is correct
27 Runtime error 1 ms 600 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 3 ms 1884 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 18 ms 7260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -