oj.uz

Submission #1069329

# Submission time Handle Problem Language Result Execution time Memory
1069329 2024-08-21T19:37:04 Z beaconmc Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 111532 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]);
        temppos[X[i]].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 355 ms 79276 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 28 ms 56668 KB Output is correct
2 Execution timed out 1014 ms 99176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 56660 KB Output is correct
2 Correct 41 ms 56668 KB Output is correct
3 Correct 203 ms 75092 KB Output is correct
4 Correct 131 ms 69208 KB Output is correct
5 Correct 255 ms 90448 KB Output is correct
6 Correct 261 ms 90452 KB Output is correct
7 Correct 265 ms 90288 KB Output is correct
8 Correct 264 ms 90220 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56656 KB Output is correct
2 Correct 44 ms 56912 KB Output is correct
3 Correct 32 ms 56660 KB Output is correct
4 Correct 31 ms 56664 KB Output is correct
5 Correct 32 ms 56668 KB Output is correct
6 Correct 35 ms 56624 KB Output is correct
7 Correct 30 ms 56656 KB Output is correct
8 Correct 32 ms 56668 KB Output is correct
9 Correct 48 ms 56812 KB Output is correct
10 Incorrect 42 ms 57180 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 30 ms 56656 KB Output is correct
2 Correct 44 ms 56912 KB Output is correct
3 Correct 32 ms 56660 KB Output is correct
4 Correct 31 ms 56664 KB Output is correct
5 Correct 32 ms 56668 KB Output is correct
6 Correct 35 ms 56624 KB Output is correct
7 Correct 30 ms 56656 KB Output is correct
8 Correct 32 ms 56668 KB Output is correct
9 Correct 48 ms 56812 KB Output is correct
10 Incorrect 42 ms 57180 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 30 ms 56656 KB Output is correct
2 Correct 44 ms 56912 KB Output is correct
3 Correct 32 ms 56660 KB Output is correct
4 Correct 31 ms 56664 KB Output is correct
5 Correct 32 ms 56668 KB Output is correct
6 Correct 35 ms 56624 KB Output is correct
7 Correct 30 ms 56656 KB Output is correct
8 Correct 32 ms 56668 KB Output is correct
9 Correct 48 ms 56812 KB Output is correct
10 Incorrect 42 ms 57180 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 59 ms 56660 KB Output is correct
2 Correct 41 ms 56668 KB Output is correct
3 Correct 203 ms 75092 KB Output is correct
4 Correct 131 ms 69208 KB Output is correct
5 Correct 255 ms 90448 KB Output is correct
6 Correct 261 ms 90452 KB Output is correct
7 Correct 265 ms 90288 KB Output is correct
8 Correct 264 ms 90220 KB Output is correct
9 Correct 443 ms 98132 KB Output is correct
10 Correct 305 ms 84160 KB Output is correct
11 Correct 676 ms 111532 KB Output is correct
12 Correct 34 ms 56548 KB Output is correct
13 Correct 33 ms 56556 KB Output is correct
14 Correct 46 ms 56652 KB Output is correct
15 Correct 34 ms 56648 KB Output is correct
16 Correct 30 ms 56660 KB Output is correct
17 Correct 31 ms 56660 KB Output is correct
18 Correct 43 ms 56716 KB Output is correct
19 Correct 43 ms 56608 KB Output is correct
20 Correct 43 ms 56760 KB Output is correct
21 Correct 45 ms 56584 KB Output is correct
22 Incorrect 531 ms 95312 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45437095688507'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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