oj.uz

Submission #1055637

# Submission time Handle Problem Language Result Execution time Memory
1055637 2024-08-13T01:42:07 Z vjudge1 Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 457520 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize(2)
set<int>fishies[3002];
ll FIS2;
ll dp[3010][2][3010],fishiess[3010][3010];
inline ll ones(int col,int len){
    return fishiess[col][len];
}
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].insert(Y[i]+1),
        fishiess[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N+1;j++)
            fishiess[i][j]+=fishiess[i][j-1];
    for(int i=1;i<=N;i++)
        fishies[i].insert(1),
        fishies[i].insert(N+1);
    fishies[N+1].insert(0);
    for(auto i:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    for(int i=2;i<=N;i++){
        for(auto rw:fishies[i]) {
            ll K=0;
            for(auto rw2: fishies[i-2]) { rw2--;
                K=max(K,max(dp[i-2][0][rw2],dp[i-2][1][rw2])+
                ones(i+1,rw-1)+ones(i-1,rw-1)-ones(i-1,min(rw-1,rw2)));
            }
            dp[i][1][rw-1]=K;
        }
        for(auto rw:fishies[i-1]) { rw--;
            for(auto rw2:fishies[i]){
                if(rw2-1>rw) break;
                ll K=ones(i+1,rw2-1)-ones(i,rw2-1)+dp[i-1][0][rw];
                dp[i][0][rw2-1]=max(dp[i][0][rw2-1],K);
            }
        }
        for(auto rw:fishies[i-1]){rw--;
            for(auto rw2: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))+dp[i-1][1][rw];
                dp[i][rw2>rw][rw2-1]=max(dp[i][rw2>rw][rw2-1],K);
            }
        }
    }

    ll ans=0;
    for(int i=0;i<=N;i++)
        ans=max({ans,dp[N][0][i],dp[N][1][i]});
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 631 ms 444976 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Runtime error 600 ms 457520 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 573 ms 432108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 1 ms 2976 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 2 ms 7772 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 1 ms 2976 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 2 ms 7772 KB Output is correct
15 Correct 3 ms 7772 KB Output is correct
16 Correct 2 ms 3548 KB Output is correct
17 Correct 169 ms 10192 KB Output is correct
18 Correct 199 ms 10180 KB Output is correct
19 Correct 129 ms 10124 KB Output is correct
20 Correct 110 ms 11664 KB Output is correct
21 Correct 105 ms 11604 KB Output is correct
22 Correct 487 ms 15496 KB Output is correct
23 Correct 12 ms 8540 KB Output is correct
24 Correct 49 ms 11796 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 7 ms 8540 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 1 ms 2976 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 2 ms 7772 KB Output is correct
15 Correct 3 ms 7772 KB Output is correct
16 Correct 2 ms 3548 KB Output is correct
17 Correct 169 ms 10192 KB Output is correct
18 Correct 199 ms 10180 KB Output is correct
19 Correct 129 ms 10124 KB Output is correct
20 Correct 110 ms 11664 KB Output is correct
21 Correct 105 ms 11604 KB Output is correct
22 Correct 487 ms 15496 KB Output is correct
23 Correct 12 ms 8540 KB Output is correct
24 Correct 49 ms 11796 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 7 ms 8540 KB Output is correct
27 Correct 38 ms 116388 KB Output is correct
28 Execution timed out 1014 ms 32524 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 573 ms 432108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 631 ms 444976 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -