oj.uz

Submission #1069275

# Submission time Handle Problem Language Result Execution time Memory
1069275 2024-08-21T18:40:52 Z beaconmc Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 112468 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];


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,M){
        Y[i]++;
        fish[X[i]].insert(Y[i]);
        weights[{X[i], Y[i]}] = W[i];
    }

    FOR(k,0,N){
        FOR(i,0,10){
            FOR(j,0,10){
            
                ll temp = 0;
                FOR(height, 0, 10){
                    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[j][height][k+1] = max(dp[j][height][k+1], dp[i][j][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]==10) cout << i << " " << j << " " << k << endl;
            }
        }
    }
    return ans;





}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 290 ms 97688 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 29 ms 83288 KB Output is correct
2 Incorrect 372 ms 112468 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '5568654479'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 83292 KB Output is correct
2 Correct 240 ms 83292 KB Output is correct
3 Correct 876 ms 93812 KB Output is correct
4 Correct 694 ms 90400 KB Output is correct
5 Execution timed out 1091 ms 102224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 83288 KB Output is correct
2 Correct 31 ms 83292 KB Output is correct
3 Correct 29 ms 83268 KB Output is correct
4 Correct 28 ms 83280 KB Output is correct
5 Correct 30 ms 83292 KB Output is correct
6 Correct 31 ms 83284 KB Output is correct
7 Correct 33 ms 83280 KB Output is correct
8 Correct 35 ms 83292 KB Output is correct
9 Correct 37 ms 83316 KB Output is correct
10 Correct 57 ms 84048 KB Output is correct
11 Correct 39 ms 83492 KB Output is correct
12 Correct 41 ms 83796 KB Output is correct
13 Correct 34 ms 83284 KB Output is correct
14 Correct 42 ms 83540 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 83288 KB Output is correct
2 Correct 31 ms 83292 KB Output is correct
3 Correct 29 ms 83268 KB Output is correct
4 Correct 28 ms 83280 KB Output is correct
5 Correct 30 ms 83292 KB Output is correct
6 Correct 31 ms 83284 KB Output is correct
7 Correct 33 ms 83280 KB Output is correct
8 Correct 35 ms 83292 KB Output is correct
9 Correct 37 ms 83316 KB Output is correct
10 Correct 57 ms 84048 KB Output is correct
11 Correct 39 ms 83492 KB Output is correct
12 Correct 41 ms 83796 KB Output is correct
13 Correct 34 ms 83284 KB Output is correct
14 Correct 42 ms 83540 KB Output is correct
15 Incorrect 30 ms 83284 KB 1st lines differ - on the 1st token, expected: '299', found: '9'
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 83288 KB Output is correct
2 Correct 31 ms 83292 KB Output is correct
3 Correct 29 ms 83268 KB Output is correct
4 Correct 28 ms 83280 KB Output is correct
5 Correct 30 ms 83292 KB Output is correct
6 Correct 31 ms 83284 KB Output is correct
7 Correct 33 ms 83280 KB Output is correct
8 Correct 35 ms 83292 KB Output is correct
9 Correct 37 ms 83316 KB Output is correct
10 Correct 57 ms 84048 KB Output is correct
11 Correct 39 ms 83492 KB Output is correct
12 Correct 41 ms 83796 KB Output is correct
13 Correct 34 ms 83284 KB Output is correct
14 Correct 42 ms 83540 KB Output is correct
15 Incorrect 30 ms 83284 KB 1st lines differ - on the 1st token, expected: '299', found: '9'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 83292 KB Output is correct
2 Correct 240 ms 83292 KB Output is correct
3 Correct 876 ms 93812 KB Output is correct
4 Correct 694 ms 90400 KB Output is correct
5 Execution timed out 1091 ms 102224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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