oj.uz

Submission #831547

# Submission time Handle Problem Language Result Execution time Memory
831547 2023-08-20T10:19:29 Z MrDeboo Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 143048 KB 
#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
map<pair<int,pair<int,int>>,long long>dp;
map<int,long long>vct[200000];
vector<int>v[200000];
int N;
long long slv(int a,int b,int c){
    if(a==N)return 0;
    if(dp.count({a,{b,c}}))return dp[{a,{b,c}}];
    // cerr<<a<<' '<<b<<endl;
    long long mx=0;
    long long tot=0;
    for(auto &i:v[a]){
        if(i<=b&&vct[a].count(i))tot-=vct[a][i];
        if(i>max(b,c)&&vct[a-1].count(i))tot+=vct[a-1][i];
        if(vct[a+1].count(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;
    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
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Execution timed out 1073 ms 143048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 45640 KB Output is correct
2 Correct 43 ms 45596 KB Output is correct
3 Correct 118 ms 58228 KB Output is correct
4 Correct 117 ms 56828 KB Output is correct
5 Correct 261 ms 73028 KB Output is correct
6 Correct 270 ms 72996 KB Output is correct
7 Correct 265 ms 72988 KB Output is correct
8 Correct 286 ms 73044 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14356 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14292 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 7 ms 14296 KB Output is correct
8 Correct 7 ms 14296 KB Output is correct
9 Correct 10 ms 14676 KB Output is correct
10 Correct 39 ms 16132 KB Output is correct
11 Correct 19 ms 15120 KB Output is correct
12 Correct 36 ms 15688 KB Output is correct
13 Correct 7 ms 14396 KB Output is correct
14 Correct 15 ms 15092 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14356 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14292 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 7 ms 14296 KB Output is correct
8 Correct 7 ms 14296 KB Output is correct
9 Correct 10 ms 14676 KB Output is correct
10 Correct 39 ms 16132 KB Output is correct
11 Correct 19 ms 15120 KB Output is correct
12 Correct 36 ms 15688 KB Output is correct
13 Correct 7 ms 14396 KB Output is correct
14 Correct 15 ms 15092 KB Output is correct
15 Correct 11 ms 14744 KB Output is correct
16 Execution timed out 1065 ms 20404 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14356 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14292 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 7 ms 14296 KB Output is correct
8 Correct 7 ms 14296 KB Output is correct
9 Correct 10 ms 14676 KB Output is correct
10 Correct 39 ms 16132 KB Output is correct
11 Correct 19 ms 15120 KB Output is correct
12 Correct 36 ms 15688 KB Output is correct
13 Correct 7 ms 14396 KB Output is correct
14 Correct 15 ms 15092 KB Output is correct
15 Correct 11 ms 14744 KB Output is correct
16 Execution timed out 1065 ms 20404 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 45640 KB Output is correct
2 Correct 43 ms 45596 KB Output is correct
3 Correct 118 ms 58228 KB Output is correct
4 Correct 117 ms 56828 KB Output is correct
5 Correct 261 ms 73028 KB Output is correct
6 Correct 270 ms 72996 KB Output is correct
7 Correct 265 ms 72988 KB Output is correct
8 Correct 286 ms 73044 KB Output is correct
9 Execution timed out 1071 ms 116312 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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