oj.uz

Submission #1056619

# Submission time Handle Problem Language Result Execution time Memory
1056619 2024-08-13T10:20:50 Z amirhoseinfar1385 Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 143948 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxh=3000+10;
int n,m;
vector<pair<int,int>>allc[maxn];
long long dpn[maxh][maxh],dps[maxh][maxh],nau[maxh][maxh],inf=1e16,all[maxh][maxh];

long long solve(){
    for(int i=0;i<=n;i++){
        nau[1][i]=0;
        dpn[1][i]=dps[1][i]=0;
    }
    long long mainres=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=n;j++){
            dpn[i][j]=dps[i][j]=0;
        }
        long long unnow=-inf;
        for(int j=n;j>=0;j--){
            dpn[i][j]=max(dpn[i][j],unnow);
            dpn[i][j]=max(dpn[i-1][j],dpn[i][j]);
            dpn[i][j]=max(dpn[i][j],dps[i-1][j]);
            if(i==n){
                mainres=max(mainres,dpn[i][j]);
            }
            unnow=max(max(unnow,dpn[i-1][j]),dps[i-1][j])+all[i][j];
        }
        unnow=0;
        for(int j=0;j<=n;j++){
            unnow=max(unnow+all[i-1][j],dps[i-1][j]);
            dps[i][j]=max(dps[i][j],unnow);
            if(i==n){
                mainres=max(mainres,dps[i][j]);
            }
        }
        unnow=0;
        for(int j=n;j>=0;j--){
            unnow=max(unnow,nau[i-1][j]);
            dps[i][j]=max(dps[i][j],unnow);
            dpn[i][j]=max(dpn[i][j],unnow);
        }
        unnow=0;
        for(int j=0;j<=n;j++){
            unnow=max(unnow+all[i-1][j],nau[i-1][j]);
            dps[i][j]=max(dps[i][j],unnow);
            dpn[i][j]=max(dpn[i][j],unnow);
        }
        unnow=0;
        for(int j=0;j<=n;j++){
            unnow+=all[i][j];
            nau[i][j]=max(dpn[i-1][j],dps[i-1][j])+unnow;
            if(i==n){
                mainres=max(mainres,nau[i][j]);
            }
        }
        for(int j=0;j<n;j++){
            if(all[i][j+1]==0){
                dpn[i][j]=nau[i][j]=dps[i][j]=-inf;
            }
        }
    }
   /* for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            cout<<dps[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            cout<<dpn[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            cout<<nau[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    return mainres;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n=N;
    m=M;
    for(int i=0;i<m;i++){
        Y[i]++;
        X[i]++;
        all[X[i]][Y[i]]+=W[i];
        allc[X[i]].push_back(make_pair(Y[i],W[i]));
    }
    for(int i=0;i<=n;i++){
        allc[i].push_back(make_pair(1,0));
        allc[i].push_back(make_pair(n,0));
        sort(allc[i].begin(),allc[i].end());
    }
    return solve();
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 143948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Execution timed out 1090 ms 140276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 121016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9304 KB Output is correct
3 Correct 2 ms 9048 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Correct 1 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 23644 KB Output is correct
10 Correct 5 ms 37980 KB Output is correct
11 Correct 3 ms 23700 KB Output is correct
12 Correct 5 ms 37972 KB Output is correct
13 Correct 2 ms 15452 KB Output is correct
14 Correct 5 ms 37980 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9304 KB Output is correct
3 Correct 2 ms 9048 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Correct 1 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 23644 KB Output is correct
10 Correct 5 ms 37980 KB Output is correct
11 Correct 3 ms 23700 KB Output is correct
12 Correct 5 ms 37972 KB Output is correct
13 Correct 2 ms 15452 KB Output is correct
14 Correct 5 ms 37980 KB Output is correct
15 Correct 4 ms 37976 KB Output is correct
16 Correct 2 ms 15452 KB Output is correct
17 Correct 12 ms 39560 KB Output is correct
18 Correct 16 ms 39772 KB Output is correct
19 Correct 23 ms 39768 KB Output is correct
20 Correct 12 ms 39772 KB Output is correct
21 Correct 12 ms 39768 KB Output is correct
22 Correct 22 ms 41300 KB Output is correct
23 Incorrect 6 ms 38236 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3057331502584'
24 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9304 KB Output is correct
3 Correct 2 ms 9048 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Correct 1 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 23644 KB Output is correct
10 Correct 5 ms 37980 KB Output is correct
11 Correct 3 ms 23700 KB Output is correct
12 Correct 5 ms 37972 KB Output is correct
13 Correct 2 ms 15452 KB Output is correct
14 Correct 5 ms 37980 KB Output is correct
15 Correct 4 ms 37976 KB Output is correct
16 Correct 2 ms 15452 KB Output is correct
17 Correct 12 ms 39560 KB Output is correct
18 Correct 16 ms 39772 KB Output is correct
19 Correct 23 ms 39768 KB Output is correct
20 Correct 12 ms 39772 KB Output is correct
21 Correct 12 ms 39768 KB Output is correct
22 Correct 22 ms 41300 KB Output is correct
23 Incorrect 6 ms 38236 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3057331502584'
24 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 121016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 143948 KB Time limit exceeded
2 Halted 0 ms 0 KB -