oj.uz

답안 #656324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656324 2022-11-06T23:56:17 Z Lobo 메기 농장 (IOI22_fish) C++17
35 / 100
 1000 ms 72016 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 = 3e3+10;
const int maxqh = 12;
const int inf = 1e18+10;

int n, m;
vector<vector<int>> dp[maxn];
// map<int,int> pf[maxn];
int pf[maxn][maxn];
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]));
        sort(all(fish[i]));
        hr[i].erase(unique(all(hr[i])),hr[i].end());
        // Store only the relevant heights

        for(int j = 0; j < hr[i].size(); j++) {
            dp[i].pb({0,0});
        }
    }

    for(int i = 1; i <= n; i++) {
        for(auto j : hr[i-1]) pf[i][j] = 0;
        for(auto j : hr[i]) pf[i][j] = 0;
        for(auto j : hr[i+1]) pf[i][j] = 0;

        for(auto aux : fish[i]) {
            int y = aux.fr;
            int w = aux.sc;
            pf[i][y]+= w;
        }
        // Do a prefix sum on the weight of the fishs
        pf[i][0] = 0;
        // for(auto it = next(pf[i].begin()); it != pf[i].end(); it++) {
        //     it->sc+= prev(it)->sc;
        // }

        for(int j = 1; j <= n; j++) {
            pf[i][j]+= pf[i][j-1];
        }
    }

    // dp[i][h0][0/1] = until i, with h[i] = hr[i][h0] 
    // and it's greater/smaller tha the previous

    // dp[1][h0][0/1] = 0
    for(int i = 0; i < hr[1].size(); i++) {
        dp[1][i][0] = 0;
        dp[1][i][1] = 0;
    }

    for(int i = 2; i <= n; i++) {
        for(int h0 = 0; h0 < hr[i].size(); h0++) {
            // It's greater than the previous
            dp[i][h0][0] = 0;
            for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
                if(hr[i-1][h1] > hr[i][h0]) continue;
                dp[i][h0][0] = max(dp[i][h0][0], dp[i-1][h1][0] + pf[i-1][hr[i][h0]]-pf[i-1][hr[i-1][h1]]);
            }

            if(i != 2) {
                for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
                    dp[i][h0][0] = max(dp[i][h0][0], dp[i-2][h2][1] + pf[i-1][max(hr[i][h0],hr[i-2][h2])]);
                    dp[i][h0][0] = max(dp[i][h0][0], dp[i-2][h2][0] + pf[i-1][max(hr[i][h0],hr[i-2][h2])]);
                }
            }
            else {
                dp[i][h0][0] = max(dp[i][h0][0], pf[i-1][hr[i][h0]]);
            }

            // It's smaller than the previous
            dp[i][h0][1] = 0;
            for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
                if(hr[i-1][h1] < hr[i][h0]) continue;
                dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][0] + pf[i][hr[i-1][h1]] - pf[i][hr[i][h0]]);
                dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][1] + pf[i][hr[i-1][h1]] - pf[i][hr[i][h0]]);
            }
        }
    }

    // cout << dp[2][hr[4].size()-1][1] << endl;

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




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

    // // dp[1][0][x] = 0;
    // for(int i = 0; i < hr[1].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 = max((int) 0,pf[i][hr[i-1][h1]]-pf[i][hr[i][h]]);

    //             for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
    //                 // fishs that 0 catchs in 1 and had not been caught by 2
    //                 // I catch every fish between h(i) and max(h(i-1),h(i-2)) + 1
    //                 int plus01 = max((int) 0, pf[i-1][hr[i][h]]-pf[i-1][max(hr[i-1][h1],hr[i-2][h2])]);
    //                 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]);
    //     }
    // }
    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:39:26: 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]
   39 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:69: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]
   69 |     for(int i = 0; i < hr[1].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:75: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]
   75 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:78:32: 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]
   78 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:84: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]
   84 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
fish.cpp:95:32: 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]
   95 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:106:24: 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]
  106 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 18480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 104 ms 36488 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 2 ms 2516 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 2 ms 2516 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 2 ms 2516 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 2 ms 2516 KB Output is correct
15 Correct 2 ms 2516 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 101 ms 7280 KB Output is correct
18 Correct 119 ms 8712 KB Output is correct
19 Correct 76 ms 8476 KB Output is correct
20 Correct 72 ms 8568 KB Output is correct
21 Correct 81 ms 8532 KB Output is correct
22 Correct 258 ms 14380 KB Output is correct
23 Correct 10 ms 3540 KB Output is correct
24 Correct 37 ms 5924 KB Output is correct
25 Correct 2 ms 2516 KB Output is correct
26 Correct 7 ms 3412 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 2 ms 2516 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 2 ms 2516 KB Output is correct
15 Correct 2 ms 2516 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 101 ms 7280 KB Output is correct
18 Correct 119 ms 8712 KB Output is correct
19 Correct 76 ms 8476 KB Output is correct
20 Correct 72 ms 8568 KB Output is correct
21 Correct 81 ms 8532 KB Output is correct
22 Correct 258 ms 14380 KB Output is correct
23 Correct 10 ms 3540 KB Output is correct
24 Correct 37 ms 5924 KB Output is correct
25 Correct 2 ms 2516 KB Output is correct
26 Correct 7 ms 3412 KB Output is correct
27 Correct 41 ms 72016 KB Output is correct
28 Execution timed out 1062 ms 38104 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 18480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -