oj.uz

Submission #1055600

# Submission time Handle Problem Language Result Execution time Memory
1055600 2024-08-12T23:28:28 Z vjudge1 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 118864 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,ll>fishies[100010];
map<int,ll>dp[100010][2];
ll ones(int col,int len){
    auto it=fishies[col].upper_bound(len);
    if(it==fishies[col].begin())return 0;
    return (--it)->second;
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
    for(int i=0;i<M;i++)
        fishies[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++){
        fishies[i][N+1];
        fishies[i][1];
        auto it=++fishies[i].begin();
        while(it!=fishies[i].end())
            it->second+=prev(it)->second,it++;
    }
    fishies[N+1][0];
    for(auto[i,j]:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    dp[0][0][0];
    for(int i=2;i<=N;i++){
        for(auto[rw,j]:fishies[i]) {
            ll K=0;
            for(auto[rw2,vl]:dp[i-2][0])
                K=max(K,vl+ones(i+1,rw-1)+max(0ll,ones(i-1,rw-1)-ones(i-1,rw2)));
            for(auto[rw2,vl]:dp[i-2][1]) 
                K=max(K,vl+ones(i+1,rw-1)+max(0ll,ones(i-1,rw-1)-ones(i-1,rw2)));
            dp[i][1][rw-1]=K;
        }
        for(auto[rw,vl]:dp[i-1][0]) {
            for(auto[rw2,j]:fishies[i]){
                if(rw2-1>j) break;
                ll K=ones(i+1,rw2-1)-ones(i,rw2-1)+vl;
                dp[i][0][rw2-1]=max(dp[i][0][rw2-1],K);
            }
        }
        for(auto[rw,vl]:dp[i-1][1]){
            for(auto[rw2,j]:fishies[i]){
                ll K=ones(i+1,rw2-1)-ones(i,min(rw,rw2-1))+
                    ones(i-1,rw2-1)-ones(i-1,min(rw2-1,rw))+vl;
                dp[i][rw2>rw][rw2-1]=max(dp[i][rw2>rw][rw2-1],K);
            }
        }
    }
    ll ans=0;
    for(auto[i,j]:dp[N][0])
        ans=max(ans,j);
    for(auto[i,j]:dp[N][1])
        ans=max(ans,j);
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 55672 KB Output is correct
2 Correct 119 ms 61604 KB Output is correct
3 Correct 39 ms 45652 KB Output is correct
4 Correct 43 ms 45660 KB Output is correct
5 Correct 573 ms 115536 KB Output is correct
6 Correct 393 ms 118864 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Execution timed out 1040 ms 52560 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 45648 KB Output is correct
2 Correct 39 ms 45652 KB Output is correct
3 Correct 54 ms 48048 KB Output is correct
4 Correct 53 ms 49488 KB Output is correct
5 Correct 88 ms 55892 KB Output is correct
6 Correct 88 ms 49096 KB Output is correct
7 Correct 77 ms 55888 KB Output is correct
8 Correct 78 ms 55892 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 7 ms 14320 KB Output is correct
6 Correct 5 ms 14288 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 4 ms 14428 KB Output is correct
9 Correct 5 ms 14684 KB Output is correct
10 Correct 15 ms 14940 KB Output is correct
11 Correct 6 ms 14684 KB Output is correct
12 Correct 8 ms 14848 KB Output is correct
13 Correct 5 ms 14424 KB Output is correct
14 Correct 7 ms 14680 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 7 ms 14320 KB Output is correct
6 Correct 5 ms 14288 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 4 ms 14428 KB Output is correct
9 Correct 5 ms 14684 KB Output is correct
10 Correct 15 ms 14940 KB Output is correct
11 Correct 6 ms 14684 KB Output is correct
12 Correct 8 ms 14848 KB Output is correct
13 Correct 5 ms 14424 KB Output is correct
14 Correct 7 ms 14680 KB Output is correct
15 Correct 5 ms 14684 KB Output is correct
16 Correct 43 ms 14896 KB Output is correct
17 Execution timed out 1073 ms 21660 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 7 ms 14320 KB Output is correct
6 Correct 5 ms 14288 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 4 ms 14428 KB Output is correct
9 Correct 5 ms 14684 KB Output is correct
10 Correct 15 ms 14940 KB Output is correct
11 Correct 6 ms 14684 KB Output is correct
12 Correct 8 ms 14848 KB Output is correct
13 Correct 5 ms 14424 KB Output is correct
14 Correct 7 ms 14680 KB Output is correct
15 Correct 5 ms 14684 KB Output is correct
16 Correct 43 ms 14896 KB Output is correct
17 Execution timed out 1073 ms 21660 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 45648 KB Output is correct
2 Correct 39 ms 45652 KB Output is correct
3 Correct 54 ms 48048 KB Output is correct
4 Correct 53 ms 49488 KB Output is correct
5 Correct 88 ms 55892 KB Output is correct
6 Correct 88 ms 49096 KB Output is correct
7 Correct 77 ms 55888 KB Output is correct
8 Correct 78 ms 55892 KB Output is correct
9 Correct 126 ms 68168 KB Output is correct
10 Correct 86 ms 46688 KB Output is correct
11 Correct 175 ms 78948 KB Output is correct
12 Correct 6 ms 14428 KB Output is correct
13 Correct 5 ms 14428 KB Output is correct
14 Correct 5 ms 14368 KB Output is correct
15 Correct 6 ms 14428 KB Output is correct
16 Correct 6 ms 14428 KB Output is correct
17 Correct 6 ms 14420 KB Output is correct
18 Correct 46 ms 45600 KB Output is correct
19 Correct 40 ms 45660 KB Output is correct
20 Correct 44 ms 45664 KB Output is correct
21 Correct 38 ms 45808 KB Output is correct
22 Correct 166 ms 73104 KB Output is correct
23 Correct 265 ms 96596 KB Output is correct
24 Correct 294 ms 98152 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 55672 KB Output is correct
2 Correct 119 ms 61604 KB Output is correct
3 Correct 39 ms 45652 KB Output is correct
4 Correct 43 ms 45660 KB Output is correct
5 Correct 573 ms 115536 KB Output is correct
6 Correct 393 ms 118864 KB Output is correct
7 Correct 5 ms 14424 KB Output is correct
8 Execution timed out 1040 ms 52560 KB Time limit exceeded
9 Halted 0 ms 0 KB -