oj.uz

Submission #661067

# Submission time Handle Problem Language Result Execution time Memory
661067 2022-11-24T07:23:00 Z mychecksedad Catfish Farm (IOI22_fish) C++17
12 / 100
 449 ms 123572 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1e5 + 100;


vector<ll> dp[N][2], pref[N][3], dp_pref[N], dp_suf[N], dp_pref_max[N]; //pref:  0 : itself, 1 : left one, 2 : right one
vector<int> v[N], p[N];

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w){  

    for(int i = 0; i < m; ++i){
        v[x[i]].pb(i);
        if(x[i] > 0) v[x[i] - 1].pb(i);
        if(x[i] < n - 1) v[x[i] + 1].pb(i);
    }

    for(int i = 0; i <= n; ++i){
        int s = v[i].size() + 1;
        p[i].pb(0);
        for(int a: v[i]) p[i].pb(y[a] + 1);
        sort(p[i].begin(), p[i].end());
        for(int k = 0; k < 3; ++k){
            pref[i][k].resize(s);
        }
        dp[i][0].resize(s);
        dp[i][1].resize(s);
        dp_pref[i].resize(s);
        dp_suf[i].resize(s);
        dp_pref_max[i].resize(s);

        vector<pair<int, int>> all;
        for(int a: v[i]) all.pb({y[a] + 1, a});
        sort(all.begin(), all.end());
        
        for(pair<int, int> &a: all){
            a.first = lower_bound(all.begin(), all.end(), make_pair(a.first, -1)) - all.begin() + 1;
            if(x[a.second] == i) pref[i][0][a.first] = w[a.second];
            else if(x[a.second] == i - 1) pref[i][1][a.first] = w[a.second];
            else pref[i][2][a.first] = w[a.second];
        }   
        for(int k = 0; k < 3; ++k)
            for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
    }

    for(int i = 0; i <= n; ++i){
        int s = pref[i][0].size();
        for(int j = 0; j < s; ++j){    
            if(i == 0){
                dp[i][0][j] = dp[i][1][j] = pref[i][2][j];
                continue;
            }

            dp[i][0][j] = pref[i][2][j];

            int pos = upper_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin() - 1;

            if(i == 1){
                dp[i][0][j] += dp_pref[i - 1][pos] + pref[i][1][j];
            }else{  
                int pos2 = upper_bound(p[i - 2].begin(), p[i - 2].end(), p[i][j]) - p[i - 2].begin() - 1;
                dp[i][0][j] += max({dp_pref[i - 1][pos] + pref[i][1][j],
                    dp_suf[i - 2][0],
                    dp_pref_max[i - 2][pos2] + pref[i][1][j] 
                });
            }
            int pos3 = lower_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin();
            dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos3 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos3]);
        }

        for(int j = 0; j < s; ++j){
            if(j == 0){
                dp_pref[i][j] = dp[i][0][j] - pref[i][2][j] - pref[i][0][j];
                dp_pref_max[i][j] = max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j];
            }
            else{
                dp_pref[i][j] = max(dp_pref[i][j - 1], dp[i][0][j] - pref[i][2][j] - pref[i][0][j]);
                dp_pref_max[i][j] = max(dp_pref_max[i][j - 1], max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j]);
            }
        }

        for(int j = s - 1; j >= 0; --j){
            if(j == s - 1){
                dp_suf[i][j] = max(dp[i][0][j], dp[i][1][j]);
            }
            else{
                dp_suf[i][j] = max({dp_suf[i][j + 1], dp[i][0][j], dp[i][1][j]});
            }
        }
    }
    return dp_suf[n][0];
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
      |                            ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos3 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos3]);
      |                                                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 62372 KB Output is correct
2 Correct 172 ms 68448 KB Output is correct
3 Correct 74 ms 51968 KB Output is correct
4 Correct 73 ms 51968 KB Output is correct
5 Correct 449 ms 123572 KB Output is correct
6 Correct 409 ms 116392 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Incorrect 249 ms 81620 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40480577213710'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 51968 KB Output is correct
2 Correct 81 ms 51996 KB Output is correct
3 Correct 122 ms 57880 KB Output is correct
4 Correct 105 ms 57908 KB Output is correct
5 Correct 166 ms 69916 KB Output is correct
6 Correct 160 ms 69904 KB Output is correct
7 Correct 167 ms 69912 KB Output is correct
8 Correct 171 ms 69916 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23708 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23736 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Incorrect 12 ms 23892 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114136648940'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23708 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23736 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Incorrect 12 ms 23892 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114136648940'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23708 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23736 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Incorrect 12 ms 23892 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114136648940'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 51968 KB Output is correct
2 Correct 81 ms 51996 KB Output is correct
3 Correct 122 ms 57880 KB Output is correct
4 Correct 105 ms 57908 KB Output is correct
5 Correct 166 ms 69916 KB Output is correct
6 Correct 160 ms 69904 KB Output is correct
7 Correct 167 ms 69912 KB Output is correct
8 Correct 171 ms 69916 KB Output is correct
9 Correct 169 ms 69916 KB Output is correct
10 Correct 128 ms 56276 KB Output is correct
11 Correct 282 ms 88760 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 13 ms 23688 KB Output is correct
14 Correct 12 ms 23804 KB Output is correct
15 Correct 14 ms 23784 KB Output is correct
16 Correct 13 ms 23732 KB Output is correct
17 Correct 14 ms 23764 KB Output is correct
18 Correct 75 ms 51936 KB Output is correct
19 Correct 73 ms 51916 KB Output is correct
20 Correct 74 ms 51916 KB Output is correct
21 Correct 73 ms 51968 KB Output is correct
22 Correct 203 ms 67900 KB Output is correct
23 Incorrect 251 ms 88816 KB 1st lines differ - on the 1st token, expected: '77772396150817', found: '81732915882581'
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 62372 KB Output is correct
2 Correct 172 ms 68448 KB Output is correct
3 Correct 74 ms 51968 KB Output is correct
4 Correct 73 ms 51968 KB Output is correct
5 Correct 449 ms 123572 KB Output is correct
6 Correct 409 ms 116392 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Incorrect 249 ms 81620 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40480577213710'
9 Halted 0 ms 0 KB -