oj.uz

Submission #661076

# Submission time Handle Problem Language Result Execution time Memory
661076 2022-11-24T08:16:09 Z mychecksedad Catfish Farm (IOI22_fish) C++17
12 / 100
 460 ms 123584 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;
        for(int a: v[i]) p[i].pb(y[a] + 1);
        p[i].pb(0);
        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:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             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 149 ms 62432 KB Output is correct
2 Correct 172 ms 68404 KB Output is correct
3 Correct 73 ms 51960 KB Output is correct
4 Correct 74 ms 51964 KB Output is correct
5 Correct 460 ms 123584 KB Output is correct
6 Correct 413 ms 116288 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 51964 KB Output is correct
2 Correct 78 ms 51964 KB Output is correct
3 Correct 119 ms 57784 KB Output is correct
4 Correct 106 ms 57920 KB Output is correct
5 Correct 170 ms 69904 KB Output is correct
6 Correct 159 ms 69896 KB Output is correct
7 Correct 166 ms 69912 KB Output is correct
8 Correct 164 ms 69920 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23700 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Incorrect 14 ms 24436 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799486576522'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23700 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Incorrect 14 ms 24436 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799486576522'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23700 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Incorrect 14 ms 24436 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799486576522'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 51964 KB Output is correct
2 Correct 78 ms 51964 KB Output is correct
3 Correct 119 ms 57784 KB Output is correct
4 Correct 106 ms 57920 KB Output is correct
5 Correct 170 ms 69904 KB Output is correct
6 Correct 159 ms 69896 KB Output is correct
7 Correct 166 ms 69912 KB Output is correct
8 Correct 164 ms 69920 KB Output is correct
9 Correct 172 ms 69936 KB Output is correct
10 Correct 121 ms 56228 KB Output is correct
11 Correct 247 ms 88752 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23812 KB Output is correct
14 Correct 12 ms 23760 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 75 ms 51848 KB Output is correct
19 Correct 73 ms 51940 KB Output is correct
20 Correct 72 ms 51940 KB Output is correct
21 Correct 76 ms 51964 KB Output is correct
22 Correct 199 ms 67740 KB Output is correct
23 Incorrect 253 ms 88752 KB 1st lines differ - on the 1st token, expected: '77772396150817', found: '81971784276762'
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 62432 KB Output is correct
2 Correct 172 ms 68404 KB Output is correct
3 Correct 73 ms 51960 KB Output is correct
4 Correct 74 ms 51964 KB Output is correct
5 Correct 460 ms 123584 KB Output is correct
6 Correct 413 ms 116288 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 257 ms 81700 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40577210384051'
9 Halted 0 ms 0 KB -