oj.uz

Submission #1069405

# Submission time Handle Problem Language Result Execution time Memory
1069405 2024-08-21T21:43:58 Z beaconmc Catfish Farm (IOI22_fish) C++17
14 / 100
 841 ms 65876 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

const ll maxn = 305;


unordered_set<ll> fish[maxn];

map<basic_string<ll>, ll> weights;

ll dp[maxn][maxn][2][2];



long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    FOR(i,0,maxn){
        FOR(j,0,maxn){

                dp[i][j][0][0] = 0;
                dp[i][j][1][0] = 0;
                dp[i][j][1][1] = 0;
                dp[i][j][0][1] = 0;

        }
    }


    FOR(i,0,M){
        Y[i]++;
        fish[X[i]].insert(Y[i]);
        weights[{X[i], Y[i]}] = W[i];
    }


    FOR(j,0,N){
        FOR(i,0,N+1){
            FOR(k,0,2){
                FOR(l,0,2){
                    if (l==1 && k==0) continue;
                    ll temp = 0;
                    if (l==1){
                        if (dp[i][j][k][l] == 0) continue;

                        FOR(height, 0, N+1){
                            if (j>0 && fish[j-1].count(height) && i < height) temp += weights[{j-1, height}];
                            if (fish[j+1].count(height)) temp += weights[{j+1, height}];
                            dp[height][j+1][k][0] = max(dp[height][j+1][k][0], dp[i][j][k][l] + temp);

                        }

                    }else{

                        FOR(height, 0, N+1){
                            
                            if (fish[j].count(height) && i >= height) temp -= weights[{j, height}];
                            if (k != 0 && j>0 && fish[j-1].count(height) && i < height) temp += weights[{j-1, height}];
                            if (fish[j+1].count(height)) temp += weights[{j+1, height}];



                            if (i != 0 && height==0){
                                dp[i][j+1][1][1] = max( dp[i][j+1][1][1], dp[i][j][k][l]+temp);
                            }
                            else if (height<i){
                                dp[height][j+1][0][0] = max(dp[height][j+1][0][0], dp[i][j][k][l]+temp);
                            }else if (height >= i) {
                                dp[height][j+1][1][0] = max(dp[height][j+1][1][0], dp[i][j][k][l]+temp);
                            }

                        }
                    }
                }
            }
        }
    }


    ll ans = 0;

    FOR(i,0,N) FOR(j,0,N+1) FOR(k,0,2) FOR(l,0,2){
        ans = max(ans, dp[i][j][k][l]);
        if (dp[i][j][k][l]==11) cout << i << " " << j << " " << k << " "<<l << endl;

    }

    return ans;





}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 34640 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 3160 KB Output is correct
2 Runtime error 143 ms 65876 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 3 ms 6492 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 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 87 ms 3420 KB Output is correct
10 Correct 841 ms 3676 KB Output is correct
11 Correct 99 ms 3420 KB Output is correct
12 Correct 627 ms 3592 KB Output is correct
13 Correct 11 ms 3164 KB Output is correct
14 Correct 592 ms 3548 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 87 ms 3420 KB Output is correct
10 Correct 841 ms 3676 KB Output is correct
11 Correct 99 ms 3420 KB Output is correct
12 Correct 627 ms 3592 KB Output is correct
13 Correct 11 ms 3164 KB Output is correct
14 Correct 592 ms 3548 KB Output is correct
15 Incorrect 516 ms 3432 KB Possible tampering with the output
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 87 ms 3420 KB Output is correct
10 Correct 841 ms 3676 KB Output is correct
11 Correct 99 ms 3420 KB Output is correct
12 Correct 627 ms 3592 KB Output is correct
13 Correct 11 ms 3164 KB Output is correct
14 Correct 592 ms 3548 KB Output is correct
15 Incorrect 516 ms 3432 KB Possible tampering with the output
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6492 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 73 ms 34640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -