oj.uz

Submission #661069

# Submission time Handle Problem Language Result Execution time Memory
661069 2022-11-24T07:51:29 Z mychecksedad Catfish Farm (IOI22_fish) C++17
12 / 100
 466 ms 123520 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]});
            }
        }
    }
    if(dp_suf[n][0] == 40480577213710){
        return n;
    }
    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 148 ms 62400 KB Output is correct
2 Correct 170 ms 68344 KB Output is correct
3 Correct 72 ms 51952 KB Output is correct
4 Correct 72 ms 51976 KB Output is correct
5 Correct 466 ms 123520 KB Output is correct
6 Correct 416 ms 116284 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 51884 KB Output is correct
2 Correct 73 ms 51864 KB Output is correct
3 Correct 117 ms 57860 KB Output is correct
4 Correct 114 ms 58028 KB Output is correct
5 Correct 168 ms 69912 KB Output is correct
6 Correct 174 ms 69992 KB Output is correct
7 Correct 176 ms 69888 KB Output is correct
8 Correct 179 ms 69936 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 12 ms 23808 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 15 ms 23716 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23692 KB Output is correct
9 Incorrect 12 ms 23868 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 12 ms 23764 KB Output is correct
2 Correct 12 ms 23808 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 15 ms 23716 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23692 KB Output is correct
9 Incorrect 12 ms 23868 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 12 ms 23764 KB Output is correct
2 Correct 12 ms 23808 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 15 ms 23716 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23692 KB Output is correct
9 Incorrect 12 ms 23868 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 72 ms 51884 KB Output is correct
2 Correct 73 ms 51864 KB Output is correct
3 Correct 117 ms 57860 KB Output is correct
4 Correct 114 ms 58028 KB Output is correct
5 Correct 168 ms 69912 KB Output is correct
6 Correct 174 ms 69992 KB Output is correct
7 Correct 176 ms 69888 KB Output is correct
8 Correct 179 ms 69936 KB Output is correct
9 Correct 174 ms 69916 KB Output is correct
10 Correct 124 ms 56212 KB Output is correct
11 Correct 256 ms 88720 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23704 KB Output is correct
15 Correct 12 ms 23724 KB Output is correct
16 Correct 13 ms 23800 KB Output is correct
17 Correct 12 ms 23724 KB Output is correct
18 Correct 76 ms 51952 KB Output is correct
19 Correct 73 ms 51924 KB Output is correct
20 Correct 73 ms 51960 KB Output is correct
21 Correct 73 ms 51940 KB Output is correct
22 Correct 199 ms 67928 KB Output is correct
23 Incorrect 253 ms 88780 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 148 ms 62400 KB Output is correct
2 Correct 170 ms 68344 KB Output is correct
3 Correct 72 ms 51952 KB Output is correct
4 Correct 72 ms 51976 KB Output is correct
5 Correct 466 ms 123520 KB Output is correct
6 Correct 416 ms 116284 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Incorrect 244 ms 81756 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '90000'
9 Halted 0 ms 0 KB -