oj.uz

Submission #1069320

# Submission time Handle Problem Language Result Execution time Memory
1069320 2024-08-21T19:28:59 Z beaconmc Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 159164 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[10][10][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,10){
        FOR(j,0,10){
            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,10){
            FOR(Y,0,10){
                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, 10){
                    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,10){
        FOR(j,0,10){
            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 238 ms 121420 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '4496835075'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98164 KB Output is correct
2 Incorrect 420 ms 141452 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '5943417035'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98100 KB Output is correct
2 Correct 66 ms 98192 KB Output is correct
3 Correct 169 ms 110620 KB Output is correct
4 Correct 138 ms 106836 KB Output is correct
5 Correct 295 ms 120972 KB Output is correct
6 Correct 314 ms 120908 KB Output is correct
7 Correct 262 ms 120824 KB Output is correct
8 Correct 270 ms 120832 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 98124 KB Output is correct
2 Correct 58 ms 98132 KB Output is correct
3 Correct 45 ms 98132 KB Output is correct
4 Correct 42 ms 98128 KB Output is correct
5 Correct 43 ms 98128 KB Output is correct
6 Correct 58 ms 98092 KB Output is correct
7 Correct 52 ms 98132 KB Output is correct
8 Correct 41 ms 98064 KB Output is correct
9 Correct 39 ms 98372 KB Output is correct
10 Correct 63 ms 98640 KB Output is correct
11 Correct 51 ms 98384 KB Output is correct
12 Correct 64 ms 98540 KB Output is correct
13 Correct 63 ms 98128 KB Output is correct
14 Correct 62 ms 98388 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 98124 KB Output is correct
2 Correct 58 ms 98132 KB Output is correct
3 Correct 45 ms 98132 KB Output is correct
4 Correct 42 ms 98128 KB Output is correct
5 Correct 43 ms 98128 KB Output is correct
6 Correct 58 ms 98092 KB Output is correct
7 Correct 52 ms 98132 KB Output is correct
8 Correct 41 ms 98064 KB Output is correct
9 Correct 39 ms 98372 KB Output is correct
10 Correct 63 ms 98640 KB Output is correct
11 Correct 51 ms 98384 KB Output is correct
12 Correct 64 ms 98540 KB Output is correct
13 Correct 63 ms 98128 KB Output is correct
14 Correct 62 ms 98388 KB Output is correct
15 Correct 63 ms 98184 KB Output is correct
16 Incorrect 46 ms 98760 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '97521743372'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 98124 KB Output is correct
2 Correct 58 ms 98132 KB Output is correct
3 Correct 45 ms 98132 KB Output is correct
4 Correct 42 ms 98128 KB Output is correct
5 Correct 43 ms 98128 KB Output is correct
6 Correct 58 ms 98092 KB Output is correct
7 Correct 52 ms 98132 KB Output is correct
8 Correct 41 ms 98064 KB Output is correct
9 Correct 39 ms 98372 KB Output is correct
10 Correct 63 ms 98640 KB Output is correct
11 Correct 51 ms 98384 KB Output is correct
12 Correct 64 ms 98540 KB Output is correct
13 Correct 63 ms 98128 KB Output is correct
14 Correct 62 ms 98388 KB Output is correct
15 Correct 63 ms 98184 KB Output is correct
16 Incorrect 46 ms 98760 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '97521743372'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98100 KB Output is correct
2 Correct 66 ms 98192 KB Output is correct
3 Correct 169 ms 110620 KB Output is correct
4 Correct 138 ms 106836 KB Output is correct
5 Correct 295 ms 120972 KB Output is correct
6 Correct 314 ms 120908 KB Output is correct
7 Correct 262 ms 120824 KB Output is correct
8 Correct 270 ms 120832 KB Output is correct
9 Correct 521 ms 131920 KB Output is correct
10 Correct 311 ms 123472 KB Output is correct
11 Correct 643 ms 148728 KB Output is correct
12 Correct 44 ms 98128 KB Output is correct
13 Correct 41 ms 98136 KB Output is correct
14 Correct 55 ms 98264 KB Output is correct
15 Correct 43 ms 98128 KB Output is correct
16 Correct 65 ms 98248 KB Output is correct
17 Correct 55 ms 98128 KB Output is correct
18 Correct 88 ms 98132 KB Output is correct
19 Correct 66 ms 98140 KB Output is correct
20 Correct 80 ms 98132 KB Output is correct
21 Correct 68 ms 98384 KB Output is correct
22 Correct 579 ms 134828 KB Output is correct
23 Execution timed out 1022 ms 159164 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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