oj.uz

Submission #1069331

# Submission time Handle Problem Language Result Execution time Memory
1069331 2024-08-21T19:37:34 Z beaconmc Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 119428 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;


unordered_set<ll> fish[maxn];

map<basic_string<ll>, ll> weights;

ll dp[6][6][maxn];

unordered_set<ll> temppos[maxn];
basic_string<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,6){
        FOR(j,0,6){
            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]);

    }
    FOR(i,0,maxn){
        for (auto&k : temppos[i]) possibles[i].push_back(k);
    }
    FOR(i,0,maxn) sort(possibles[i].begin(), possibles[i].end());

    FOR(k,0,N){
        FOR(X,0,6){
            FOR(Y,0,6){
                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;
                set<ll> visited;

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

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

                    for (auto&p : fish[k]){
                        if (visited.count(p)==0 && j >= p && p<=height){
                            temp -= weights[{k, p}];
                            visited.insert(p);
                        }
                    }

                    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,6){
        FOR(j,0,6){
            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:52:51: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   52 |                 if (k>=2 && possibles[k-2].size() <= X) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:54:51: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   54 |                 if (k>=1 && possibles[k-1].size() <= Y) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:63:45: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   63 |                     if (possibles[k].size() <= Z) continue;
      |                         ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56656 KB Output is correct
2 Incorrect 935 ms 97052 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '3466016543'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 56776 KB Output is correct
2 Correct 44 ms 56664 KB Output is correct
3 Correct 167 ms 75088 KB Output is correct
4 Correct 109 ms 68944 KB Output is correct
5 Correct 276 ms 90364 KB Output is correct
6 Correct 258 ms 90448 KB Output is correct
7 Correct 287 ms 90452 KB Output is correct
8 Correct 264 ms 90448 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56632 KB Output is correct
2 Correct 28 ms 56668 KB Output is correct
3 Correct 27 ms 56664 KB Output is correct
4 Correct 28 ms 56656 KB Output is correct
5 Correct 31 ms 56668 KB Output is correct
6 Correct 32 ms 56624 KB Output is correct
7 Correct 29 ms 56656 KB Output is correct
8 Correct 29 ms 56768 KB Output is correct
9 Correct 37 ms 56916 KB Output is correct
10 Incorrect 42 ms 57120 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '506996315567'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56632 KB Output is correct
2 Correct 28 ms 56668 KB Output is correct
3 Correct 27 ms 56664 KB Output is correct
4 Correct 28 ms 56656 KB Output is correct
5 Correct 31 ms 56668 KB Output is correct
6 Correct 32 ms 56624 KB Output is correct
7 Correct 29 ms 56656 KB Output is correct
8 Correct 29 ms 56768 KB Output is correct
9 Correct 37 ms 56916 KB Output is correct
10 Incorrect 42 ms 57120 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '506996315567'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56632 KB Output is correct
2 Correct 28 ms 56668 KB Output is correct
3 Correct 27 ms 56664 KB Output is correct
4 Correct 28 ms 56656 KB Output is correct
5 Correct 31 ms 56668 KB Output is correct
6 Correct 32 ms 56624 KB Output is correct
7 Correct 29 ms 56656 KB Output is correct
8 Correct 29 ms 56768 KB Output is correct
9 Correct 37 ms 56916 KB Output is correct
10 Incorrect 42 ms 57120 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '506996315567'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 56776 KB Output is correct
2 Correct 44 ms 56664 KB Output is correct
3 Correct 167 ms 75088 KB Output is correct
4 Correct 109 ms 68944 KB Output is correct
5 Correct 276 ms 90364 KB Output is correct
6 Correct 258 ms 90448 KB Output is correct
7 Correct 287 ms 90452 KB Output is correct
8 Correct 264 ms 90448 KB Output is correct
9 Correct 355 ms 95092 KB Output is correct
10 Correct 327 ms 84188 KB Output is correct
11 Correct 655 ms 111600 KB Output is correct
12 Correct 33 ms 56668 KB Output is correct
13 Correct 41 ms 56660 KB Output is correct
14 Correct 27 ms 56668 KB Output is correct
15 Correct 28 ms 56660 KB Output is correct
16 Correct 33 ms 56772 KB Output is correct
17 Correct 32 ms 56656 KB Output is correct
18 Correct 39 ms 56664 KB Output is correct
19 Correct 55 ms 56656 KB Output is correct
20 Correct 42 ms 56668 KB Output is correct
21 Correct 41 ms 56660 KB Output is correct
22 Correct 369 ms 90708 KB Output is correct
23 Correct 972 ms 118040 KB Output is correct
24 Execution timed out 1014 ms 119428 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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