oj.uz

Submission #661062

# Submission time Handle Problem Language Result Execution time Memory
661062 2022-11-24T07:12:20 Z mychecksedad Catfish Farm (IOI22_fish) C++17
0 / 100
 434 ms 165476 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[pos2][j] + pref[i][1][j] 
                });
            }

            dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos + 1 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos + 1]);
        }

        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 max(dp[n][0][0], dp[n][1][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:68: 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] + (pos + 1 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos + 1]);
      |                                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 62380 KB Output is correct
2 Correct 176 ms 68392 KB Output is correct
3 Correct 73 ms 51848 KB Output is correct
4 Correct 71 ms 51968 KB Output is correct
5 Incorrect 434 ms 123492 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '1495520842124514'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Runtime error 262 ms 165476 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 51876 KB Output is correct
2 Correct 71 ms 51968 KB Output is correct
3 Incorrect 123 ms 57848 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21261930173730'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 51876 KB Output is correct
2 Correct 71 ms 51968 KB Output is correct
3 Incorrect 123 ms 57848 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21261930173730'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 62380 KB Output is correct
2 Correct 176 ms 68392 KB Output is correct
3 Correct 73 ms 51848 KB Output is correct
4 Correct 71 ms 51968 KB Output is correct
5 Incorrect 434 ms 123492 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '1495520842124514'
6 Halted 0 ms 0 KB -