oj.uz

Submission #1069322

# Submission time Handle Problem Language Result Execution time Memory
1069322 2024-08-21T19:30:02 Z beaconmc Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 127568 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 = 100005;


set<ll> fish[maxn];

map<vector<ll>, ll> weights;

ll dp[8][8][maxn];

set<ll> temppos[maxn];
vector<ll> possibles[maxn];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    FOR(i,0,8){
        FOR(j,0,8){
            FOR(k,0,maxn){
                dp[i][j][k] = 0;
            }
        }
    }
    FOR(i,0,maxn) temppos[i].insert(0);


    FOR(i,0,M){
        Y[i]++;
        fish[X[i]].insert(Y[i]);
        weights[{X[i], Y[i]}] = W[i];
        if (X[i] > 0) temppos[X[i]-1].insert(Y[i]);
        temppos[X[i]+1].insert(Y[i]);
        temppos[X[i]].insert(Y[i]);
    }
    FOR(i,0,maxn){
        for (auto&k : temppos[i]) possibles[i].push_back(k);
    }

    FOR(k,0,N){
        FOR(X,0,8){
            FOR(Y,0,8){
                ll i=0,j=0;
 
                if (k>=2 && possibles[k-2].size() <= X) continue;
                else if (k>=2) i = possibles[k-2][X];
                if (k>=1 && possibles[k-1].size() <= Y) continue;
                else if (k>=1) j  = possibles[k-1][Y];
                


                ll temp = 0;
                FOR(Z, 0, 8){
                    if (possibles[k].size() <= Z) continue;
                    ll height = possibles[k][Z];

                    if (fish[k+1].count(height)) temp += weights[{k+1, height}];

                    if (fish[k].count(height) && j>=height) temp -= weights[{k, height}];

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

                    dp[Y][Z][k+1] = max(dp[Y][Z][k+1], dp[X][Y][k] + temp);
                }
            }
        }
    }




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

            }
        }
    }
    return ans;





}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:51:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   51 |                 if (k>=2 && possibles[k-2].size() <= X) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:53:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   53 |                 if (k>=1 && possibles[k-1].size() <= Y) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:60:45: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   60 |                     if (possibles[k].size() <= Z) continue;
      |                         ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 93232 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '3309025585'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 69980 KB Output is correct
2 Incorrect 337 ms 113328 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '4748330365'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 69972 KB Output is correct
2 Correct 71 ms 69968 KB Output is correct
3 Correct 133 ms 82512 KB Output is correct
4 Correct 129 ms 78660 KB Output is correct
5 Correct 231 ms 92756 KB Output is correct
6 Correct 254 ms 92676 KB Output is correct
7 Correct 243 ms 92740 KB Output is correct
8 Correct 266 ms 92800 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70012 KB Output is correct
2 Correct 32 ms 70084 KB Output is correct
3 Correct 32 ms 69872 KB Output is correct
4 Correct 41 ms 69972 KB Output is correct
5 Correct 35 ms 69968 KB Output is correct
6 Correct 32 ms 69988 KB Output is correct
7 Correct 48 ms 69892 KB Output is correct
8 Correct 34 ms 69892 KB Output is correct
9 Correct 35 ms 70128 KB Output is correct
10 Incorrect 76 ms 70480 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '702028901154'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70012 KB Output is correct
2 Correct 32 ms 70084 KB Output is correct
3 Correct 32 ms 69872 KB Output is correct
4 Correct 41 ms 69972 KB Output is correct
5 Correct 35 ms 69968 KB Output is correct
6 Correct 32 ms 69988 KB Output is correct
7 Correct 48 ms 69892 KB Output is correct
8 Correct 34 ms 69892 KB Output is correct
9 Correct 35 ms 70128 KB Output is correct
10 Incorrect 76 ms 70480 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '702028901154'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70012 KB Output is correct
2 Correct 32 ms 70084 KB Output is correct
3 Correct 32 ms 69872 KB Output is correct
4 Correct 41 ms 69972 KB Output is correct
5 Correct 35 ms 69968 KB Output is correct
6 Correct 32 ms 69988 KB Output is correct
7 Correct 48 ms 69892 KB Output is correct
8 Correct 34 ms 69892 KB Output is correct
9 Correct 35 ms 70128 KB Output is correct
10 Incorrect 76 ms 70480 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '702028901154'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 69972 KB Output is correct
2 Correct 71 ms 69968 KB Output is correct
3 Correct 133 ms 82512 KB Output is correct
4 Correct 129 ms 78660 KB Output is correct
5 Correct 231 ms 92756 KB Output is correct
6 Correct 254 ms 92676 KB Output is correct
7 Correct 243 ms 92740 KB Output is correct
8 Correct 266 ms 92800 KB Output is correct
9 Correct 468 ms 103760 KB Output is correct
10 Correct 295 ms 93516 KB Output is correct
11 Correct 652 ms 117008 KB Output is correct
12 Correct 33 ms 69976 KB Output is correct
13 Correct 51 ms 69972 KB Output is correct
14 Correct 43 ms 70052 KB Output is correct
15 Correct 36 ms 70068 KB Output is correct
16 Correct 33 ms 69980 KB Output is correct
17 Correct 33 ms 69884 KB Output is correct
18 Correct 51 ms 69992 KB Output is correct
19 Correct 48 ms 69980 KB Output is correct
20 Correct 59 ms 69980 KB Output is correct
21 Correct 74 ms 69968 KB Output is correct
22 Correct 544 ms 104600 KB Output is correct
23 Execution timed out 1030 ms 127568 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 93232 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '3309025585'
2 Halted 0 ms 0 KB -