oj.uz

Submission #1069328

# Submission time Handle Problem Language Result Execution time Memory
1069328 2024-08-21T19:34:44 Z beaconmc Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 141908 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


#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[8][8][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,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(i,0,maxn) sort(possibles[i].begin(), possibles[i].end());

    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:56: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]
   56 |                 if (k>=2 && possibles[k-2].size() <= X) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:58: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]
   58 |                 if (k>=1 && possibles[k-1].size() <= Y) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:65: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]
   65 |                     if (possibles[k].size() <= Z) continue;
      |                         ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 100988 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 49 ms 78676 KB Output is correct
2 Incorrect 310 ms 121228 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 71 ms 78596 KB Output is correct
2 Correct 88 ms 78928 KB Output is correct
3 Correct 184 ms 96852 KB Output is correct
4 Correct 126 ms 91220 KB Output is correct
5 Correct 314 ms 112396 KB Output is correct
6 Correct 277 ms 112256 KB Output is correct
7 Correct 308 ms 112208 KB Output is correct
8 Correct 291 ms 112168 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 78604 KB Output is correct
2 Correct 57 ms 78676 KB Output is correct
3 Correct 48 ms 78676 KB Output is correct
4 Correct 49 ms 78588 KB Output is correct
5 Correct 45 ms 78464 KB Output is correct
6 Correct 65 ms 78676 KB Output is correct
7 Correct 47 ms 78528 KB Output is correct
8 Correct 46 ms 78676 KB Output is correct
9 Correct 59 ms 78672 KB Output is correct
10 Incorrect 56 ms 79136 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 43 ms 78604 KB Output is correct
2 Correct 57 ms 78676 KB Output is correct
3 Correct 48 ms 78676 KB Output is correct
4 Correct 49 ms 78588 KB Output is correct
5 Correct 45 ms 78464 KB Output is correct
6 Correct 65 ms 78676 KB Output is correct
7 Correct 47 ms 78528 KB Output is correct
8 Correct 46 ms 78676 KB Output is correct
9 Correct 59 ms 78672 KB Output is correct
10 Incorrect 56 ms 79136 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 43 ms 78604 KB Output is correct
2 Correct 57 ms 78676 KB Output is correct
3 Correct 48 ms 78676 KB Output is correct
4 Correct 49 ms 78588 KB Output is correct
5 Correct 45 ms 78464 KB Output is correct
6 Correct 65 ms 78676 KB Output is correct
7 Correct 47 ms 78528 KB Output is correct
8 Correct 46 ms 78676 KB Output is correct
9 Correct 59 ms 78672 KB Output is correct
10 Incorrect 56 ms 79136 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 71 ms 78596 KB Output is correct
2 Correct 88 ms 78928 KB Output is correct
3 Correct 184 ms 96852 KB Output is correct
4 Correct 126 ms 91220 KB Output is correct
5 Correct 314 ms 112396 KB Output is correct
6 Correct 277 ms 112256 KB Output is correct
7 Correct 308 ms 112208 KB Output is correct
8 Correct 291 ms 112168 KB Output is correct
9 Correct 423 ms 120148 KB Output is correct
10 Correct 308 ms 106324 KB Output is correct
11 Correct 631 ms 133456 KB Output is correct
12 Correct 56 ms 78616 KB Output is correct
13 Correct 52 ms 78672 KB Output is correct
14 Correct 52 ms 78696 KB Output is correct
15 Correct 52 ms 78672 KB Output is correct
16 Correct 53 ms 78676 KB Output is correct
17 Correct 56 ms 78680 KB Output is correct
18 Correct 62 ms 78672 KB Output is correct
19 Correct 72 ms 78672 KB Output is correct
20 Correct 63 ms 78676 KB Output is correct
21 Correct 77 ms 78676 KB Output is correct
22 Correct 518 ms 117420 KB Output is correct
23 Correct 949 ms 141392 KB Output is correct
24 Execution timed out 1046 ms 141908 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 100988 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '3309025585'
2 Halted 0 ms 0 KB -