oj.uz

Submission #831513

# Submission time Handle Problem Language Result Execution time Memory
831513 2023-08-20T10:04:14 Z MrDeboo Catfish Farm (IOI22_fish) C++17
17 / 100
 1000 ms 239072 KB 
#include "fish.h"
#include "bits/stdc++.h"
#define int long long
using namespace std;
int dp[311][311][311];
int vct[311][311];
int vctt[311][311];
vector<int>v[311];
int N;
int slv(int a,int b,int c){
    if(a==N)return 0;
    if(dp[a][b][c]!=-1)return dp[a][b][c];
    // cerr<<a<<' '<<b<<endl;
    int mx=0;
    int tot=0;
    for(auto &i:v[a]){
        if(i<=b)tot-=vct[a][i];
        if(i>max(b,c))tot+=vct[a-1][i];
        tot+=vct[a+1][i];
        mx=max(mx,slv(a+1,i,b)+tot);
    }
    return dp[a][b][c]=mx;
}
long long max_weights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y, std::vector<int32_t> w) {
    N=n;
    if(n>300){
        int g=0;
        for(auto &i:w)g+=i;
        return g;
    }
    memset(dp,-1,sizeof dp);
    for(int i=0;i<=n;i++)v[i].push_back(0);
    for(int i=0;i<m;i++){
        vct[x[i]][y[i]+1]=w[i];
        if(x[i])v[x[i]-1].push_back(y[i]+1);
        v[x[i]].push_back(y[i]+1);
        v[x[i]+1].push_back(y[i]+1);
    }
    for(int i=0;i<=n;i++)sort(v[i].begin(),v[i].end());
    for(int i=0;i<=n;i++)v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
    return slv(0,0,0);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2124 KB Output is correct
2 Correct 22 ms 2640 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 67 ms 7288 KB Output is correct
6 Correct 72 ms 7296 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 235720 KB Output is correct
2 Incorrect 36 ms 4016 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 11 ms 1472 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 235684 KB Output is correct
2 Correct 74 ms 235716 KB Output is correct
3 Correct 74 ms 235700 KB Output is correct
4 Correct 85 ms 235724 KB Output is correct
5 Correct 74 ms 235644 KB Output is correct
6 Correct 75 ms 235708 KB Output is correct
7 Correct 76 ms 235728 KB Output is correct
8 Correct 76 ms 235728 KB Output is correct
9 Correct 83 ms 236064 KB Output is correct
10 Correct 78 ms 236624 KB Output is correct
11 Correct 77 ms 236192 KB Output is correct
12 Correct 77 ms 236588 KB Output is correct
13 Correct 75 ms 235844 KB Output is correct
14 Correct 83 ms 236556 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 235684 KB Output is correct
2 Correct 74 ms 235716 KB Output is correct
3 Correct 74 ms 235700 KB Output is correct
4 Correct 85 ms 235724 KB Output is correct
5 Correct 74 ms 235644 KB Output is correct
6 Correct 75 ms 235708 KB Output is correct
7 Correct 76 ms 235728 KB Output is correct
8 Correct 76 ms 235728 KB Output is correct
9 Correct 83 ms 236064 KB Output is correct
10 Correct 78 ms 236624 KB Output is correct
11 Correct 77 ms 236192 KB Output is correct
12 Correct 77 ms 236588 KB Output is correct
13 Correct 75 ms 235844 KB Output is correct
14 Correct 83 ms 236556 KB Output is correct
15 Correct 76 ms 236528 KB Output is correct
16 Correct 147 ms 235904 KB Output is correct
17 Execution timed out 1093 ms 239072 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 235684 KB Output is correct
2 Correct 74 ms 235716 KB Output is correct
3 Correct 74 ms 235700 KB Output is correct
4 Correct 85 ms 235724 KB Output is correct
5 Correct 74 ms 235644 KB Output is correct
6 Correct 75 ms 235708 KB Output is correct
7 Correct 76 ms 235728 KB Output is correct
8 Correct 76 ms 235728 KB Output is correct
9 Correct 83 ms 236064 KB Output is correct
10 Correct 78 ms 236624 KB Output is correct
11 Correct 77 ms 236192 KB Output is correct
12 Correct 77 ms 236588 KB Output is correct
13 Correct 75 ms 235844 KB Output is correct
14 Correct 83 ms 236556 KB Output is correct
15 Correct 76 ms 236528 KB Output is correct
16 Correct 147 ms 235904 KB Output is correct
17 Execution timed out 1093 ms 239072 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 11 ms 1472 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2124 KB Output is correct
2 Correct 22 ms 2640 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 67 ms 7288 KB Output is correct
6 Correct 72 ms 7296 KB Output is correct
7 Correct 73 ms 235720 KB Output is correct
8 Incorrect 36 ms 4016 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
9 Halted 0 ms 0 KB -