oj.uz

Submission #652690

# Submission time Handle Problem Language Result Execution time Memory
652690 2022-10-23T20:50:35 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 136052 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int maxn = 1e5+10;
const int maxqh = 12;
const int inf = 1e18+10;

int n, m, dp[maxn][maxqh][maxqh];
vector<pair<int,int>> fish[maxn]; // fishs from column i
vector<int> hr[maxn]; // important heights from column i, the ones that can be chosen

long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) {
    n = N;
    m = M;

    for(int i = 0; i < m; i++) {
        fish[X[i]+1].pb(mp(Y[i]+1,W[i]));
        hr[X[i]+1].pb(Y[i]);
    }

    for(int i = 0; i <= n; i++) {
        hr[i].pb(0);
        hr[i].pb(n);
        sort(all(hr[i]));
        hr[i].erase(unique(all(hr[i])),hr[i].end());
    }

    // dp[i][h1][h] = until i and with h[i-1] = hr[i-1][h1] and h[i] = hr[i][h-1]

    // dp[1][0][x] = 0;
    for(int i = 0; i < hr[i].size(); i++) dp[1][0][i] = 0;
    for(int i = 2; i <= n; i++) {
        for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
            for(int h = 0; h < hr[i].size(); h++) {
                dp[i][h1][h] = 0;

                int plus10 = 0; // fishs that 1 catchs in 0
                for(auto aux : fish[i]) {
                    int y = aux.fr;
                    int w = aux.sc;
                    if(y > hr[i][h] && y <= hr[i-1][h1]) plus10+= w;
                }

                for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
                    int plus01 = 0; // fishs that 0 catchs in 1 and had not been caught by 2

                    for(auto aux : fish[i-1]) {
                        int y = aux.fr;
                        int w = aux.sc;
                        if(y > hr[i-1][h1] && y <= hr[i][h] && y > hr[i-2][h2]) plus01+= w;
                    }
                    dp[i][h1][h] = max(dp[i][h1][h],dp[i-1][h2][h1]+plus01 + plus10);
                }
            }
        }
    }

    int ans = 0;
    for(int h = 0; h < hr[n].size(); h++) {
        for(int h1 = 0; h1 < hr[n-1].size(); h1++) {
            ans = max(ans,dp[n][h1][h]);
        }
    }

    // // dp[i][h1][h] = until i and with h[i-1] = h1 and h[i] = h

    // // dp[1][0][h] = 0;
    // for(int i = 0; i <= maxh-1; i++) dp[1][0][i] = 0;
    // for(int i = 2; i <= n; i++) {
    //     for(int h1 = 0; h1 <= maxh-1; h1++) {
    //         for(int h = 0; h <= maxh-1; h++) {
    //             dp[i][h1][h] = 0;

    //             int plus10 = 0; // fishs that 1 catchs in 0
    //             for(auto aux : fish[i]) {
    //                 int y = aux.fr;
    //                 int w = aux.sc;
    //                 if(y > h && y <= h1) plus10+= w;
    //             }

    //             for(int h2 = 0; h2 <= maxh-1; h2++) {
    //                 int plus01 = 0; // fishs that 0 catchs in 1 and had not been caught by 2

    //                 for(auto aux : fish[i-1]) {
    //                     int y = aux.fr;
    //                     int w = aux.sc;
    //                     if(y > h1 && y <= h && y > h2) plus01+= w;
    //                 }
    //                 dp[i][h1][h] = max(dp[i][h1][h],dp[i-1][h2][h1]+plus01 + plus10);
    //             }
    //         }
    //     }
    // }

    // int ans = 0;
    // for(int h = 0; h <= maxh-1; h++) {
    //     for(int h1 = 0; h1 <= maxh-1; h1++) {
    //         ans = max(ans,dp[n][h1][h]);
    //     }
    // }
    return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:38:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < hr[i].size(); i++) dp[1][0][i] = 0;
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:40:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                         ~~~^~~~~~~~~~~~~~~~
fish.cpp:41:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int h = 0; h < hr[i].size(); h++) {
      |                            ~~^~~~~~~~~~~~~~
fish.cpp:51:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
fish.cpp:66:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int h = 0; h < hr[n].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:67:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int h1 = 0; h1 < hr[n-1].size(); h1++) {
      |                         ~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 12080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1098 ms 15600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 120776 KB Output is correct
2 Correct 56 ms 120792 KB Output is correct
3 Correct 93 ms 113532 KB Output is correct
4 Correct 73 ms 123344 KB Output is correct
5 Correct 127 ms 130920 KB Output is correct
6 Correct 118 ms 131020 KB Output is correct
7 Correct 122 ms 131112 KB Output is correct
8 Correct 119 ms 130980 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 10 ms 5496 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5332 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 10 ms 5496 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5332 KB Output is correct
15 Correct 3 ms 5336 KB Output is correct
16 Incorrect 583 ms 5188 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '107468939232283'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 10 ms 5496 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5332 KB Output is correct
15 Correct 3 ms 5336 KB Output is correct
16 Incorrect 583 ms 5188 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '107468939232283'
17 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 120776 KB Output is correct
2 Correct 56 ms 120792 KB Output is correct
3 Correct 93 ms 113532 KB Output is correct
4 Correct 73 ms 123344 KB Output is correct
5 Correct 127 ms 130920 KB Output is correct
6 Correct 118 ms 131020 KB Output is correct
7 Correct 122 ms 131112 KB Output is correct
8 Correct 119 ms 130980 KB Output is correct
9 Correct 122 ms 130924 KB Output is correct
10 Correct 82 ms 69056 KB Output is correct
11 Correct 191 ms 133176 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 54 ms 120712 KB Output is correct
19 Correct 53 ms 120780 KB Output is correct
20 Correct 55 ms 120740 KB Output is correct
21 Correct 57 ms 120824 KB Output is correct
22 Correct 128 ms 129060 KB Output is correct
23 Correct 213 ms 134308 KB Output is correct
24 Correct 217 ms 136052 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 12080 KB Time limit exceeded
2 Halted 0 ms 0 KB -