oj.uz

Submission #831536

# Submission time Handle Problem Language Result Execution time Memory
831536 2023-08-20T10:15:56 Z MrDeboo Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 167324 KB 
#include "fish.h"
#include "bits/stdc++.h"
#define int long long
using namespace std;
map<pair<int,pair<int,int>>,int>dp;
map<int,int>vct[200000];
vector<int>v[200000];
int N;
int 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;
    int mx=0;
    int 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 1092 ms 167324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 50308 KB Output is correct
2 Correct 39 ms 50344 KB Output is correct
3 Correct 114 ms 66504 KB Output is correct
4 Correct 109 ms 65088 KB Output is correct
5 Correct 274 ms 86220 KB Output is correct
6 Correct 284 ms 85592 KB Output is correct
7 Correct 275 ms 86056 KB Output is correct
8 Correct 268 ms 86328 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 7 ms 14392 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14388 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14376 KB Output is correct
9 Correct 9 ms 14756 KB Output is correct
10 Correct 36 ms 16628 KB Output is correct
11 Correct 19 ms 15288 KB Output is correct
12 Correct 28 ms 16072 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 15 ms 15300 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 7 ms 14392 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14388 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14376 KB Output is correct
9 Correct 9 ms 14756 KB Output is correct
10 Correct 36 ms 16628 KB Output is correct
11 Correct 19 ms 15288 KB Output is correct
12 Correct 28 ms 16072 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 15 ms 15300 KB Output is correct
15 Correct 9 ms 14872 KB Output is correct
16 Execution timed out 1092 ms 21388 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 7 ms 14392 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14388 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14376 KB Output is correct
9 Correct 9 ms 14756 KB Output is correct
10 Correct 36 ms 16628 KB Output is correct
11 Correct 19 ms 15288 KB Output is correct
12 Correct 28 ms 16072 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 15 ms 15300 KB Output is correct
15 Correct 9 ms 14872 KB Output is correct
16 Execution timed out 1092 ms 21388 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 50308 KB Output is correct
2 Correct 39 ms 50344 KB Output is correct
3 Correct 114 ms 66504 KB Output is correct
4 Correct 109 ms 65088 KB Output is correct
5 Correct 274 ms 86220 KB Output is correct
6 Correct 284 ms 85592 KB Output is correct
7 Correct 275 ms 86056 KB Output is correct
8 Correct 268 ms 86328 KB Output is correct
9 Execution timed out 1065 ms 148472 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 1092 ms 167324 KB Time limit exceeded
2 Halted 0 ms 0 KB -