oj.uz

Submission #743962

# Submission time Handle Problem Language Result Execution time Memory
743962 2023-05-18T06:45:25 Z MilosMilutinovic Catfish Farm (IOI22_fish) C++17
18 / 100
 418 ms 89392 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
int sz[N];
vector<int> v[N];
vector<pair<int, int>> my[N];
vector<ll> dpinc[N];
vector<ll> dpdec[N];
vector<ll> pref[N];
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {
    for (int i = 1; i <= n; i++)
        v[i].push_back(0);
    for (int i = 0; i < m; i++) {
        x[i]++; y[i]++;
        v[x[i] - 1].push_back(y[i]);
        v[x[i] + 1].push_back(y[i]);
        v[x[i]].push_back(y[i]);
        my[x[i]].emplace_back(y[i], w[i]);
    }
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end());
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
        sz[i] = (int) v[i].size();
        dpinc[i].resize(sz[i]);
        dpdec[i].resize(sz[i]);
        pref[i].resize(sz[i]);
        for (auto& p : my[i]) {
            int idx = (int) (lower_bound(v[i].begin(), v[i].end(), p.first) - v[i].begin());
            pref[i][idx] += p.second;
        }
        for (int j = 1; j < sz[i]; j++) pref[i][j] += pref[i][j - 1];
    }
    {
        // build dpdec 1
        int ptr = 0;
        ll s = 0;
        for (int j = 0; j < sz[1]; j++) {
            while (ptr < sz[2] && v[2][ptr] <= v[1][j]) {
                s = pref[2][ptr];
                ptr++;
            }
            dpdec[1][j] = s;
        }
    }
    for (int i = 2; i <= n; i++) {
        {
            // inc -> inc
            ll mx = 0;
            ll s = 0;
            int ptr = 0;
            for (int j = 0; j < sz[i]; j++) {
                while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
                    s = pref[i - 1][ptr];
                    mx = max(mx, dpinc[i - 1][ptr] - pref[i - 1][ptr]);
                    ptr++;
                }
                dpinc[i][j] = mx + s;
            }
        }
        {
            // dec -> dec
            ll mx = 0;
            int ptr = sz[i - 1] - 1;
            for (int j = sz[i] - 1; j >= 0; j--) {
                while (ptr >= 0 && v[i - 1][ptr] >= v[i][j]) {
                    mx = max(mx, dpdec[i - 1][ptr]);
                    ptr--;
                }
                dpdec[i][j] = mx - pref[i][j];
            }
        }
        {
            // my inc -> my dec
            for (int j = 0; j < sz[i]; j++) dpdec[i][j] = max(dpdec[i][j], dpinc[i][j]);
        }
        if (i > 2) {
            // connect with i - 2
            {
                // i - 2 is greater
                ll mx = 0;
                for (int j = 0; j < sz[i - 2]; j++) mx = max(mx, dpdec[i - 2][j]);
                int ptr = 0;
                ll s = 0;
                for (int j = 0; j < sz[i]; j++) {
                    while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
                        s = pref[i - 1][ptr];
                        ptr++;
                    }
                    dpdec[i][j] = max(dpdec[i][j], mx - s);
                }
            }
            {
                ll mx = 0;
                int ptr = 0;
                ll s = 0;
                for (int j = 0; j < sz[i - 2]; j++) {
                    while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i - 2][j]) {
                        s = pref[i - 1][ptr];
                        ptr++;
                    }
                    mx = max(mx, dpdec[i - 2][j] - s);
                }
                ptr = 0;
                s = 0;
                for (int j = 0; j < sz[i]; j++) {
                    while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
                        s = pref[i - 1][ptr];
                        ptr++;
                    }
                    dpdec[i][j] = max(dpdec[i][j], mx + s);
                }
            }
        }
        {
            // add right to dpdec
            int ptr = 0;
            ll s = 0;
            for (int j = 0; j < sz[i]; j++) {
                while (ptr < sz[i + 1] && v[i + 1][ptr] <= v[i][j]) {
                    s = pref[i + 1][ptr];
                    ptr++;
                }
                dpdec[i][j] += s;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < sz[i]; j++)
            ans = max(ans, dpdec[i][j]);
    return ans;
}

/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 54380 KB Output is correct
2 Correct 102 ms 59116 KB Output is correct
3 Correct 47 ms 48332 KB Output is correct
4 Correct 40 ms 48340 KB Output is correct
5 Correct 267 ms 89392 KB Output is correct
6 Correct 418 ms 87756 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35412 KB Output is correct
2 Correct 164 ms 63040 KB Output is correct
3 Correct 179 ms 67644 KB Output is correct
4 Correct 90 ms 55764 KB Output is correct
5 Correct 105 ms 59200 KB Output is correct
6 Correct 20 ms 35520 KB Output is correct
7 Correct 19 ms 35584 KB Output is correct
8 Correct 22 ms 35500 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 41 ms 48332 KB Output is correct
11 Correct 43 ms 48360 KB Output is correct
12 Correct 97 ms 57776 KB Output is correct
13 Correct 121 ms 61500 KB Output is correct
14 Correct 95 ms 56928 KB Output is correct
15 Correct 112 ms 57360 KB Output is correct
16 Correct 111 ms 56936 KB Output is correct
17 Correct 112 ms 59112 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 48428 KB Output is correct
2 Correct 42 ms 48340 KB Output is correct
3 Correct 71 ms 50892 KB Output is correct
4 Correct 71 ms 51008 KB Output is correct
5 Correct 126 ms 55640 KB Output is correct
6 Correct 113 ms 54860 KB Output is correct
7 Correct 133 ms 55380 KB Output is correct
8 Correct 141 ms 55420 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35524 KB Output is correct
2 Correct 19 ms 35452 KB Output is correct
3 Correct 22 ms 35476 KB Output is correct
4 Correct 19 ms 35456 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 18 ms 35480 KB Output is correct
7 Correct 22 ms 35620 KB Output is correct
8 Correct 20 ms 35412 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 19 ms 35668 KB Output is correct
11 Incorrect 19 ms 35540 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35524 KB Output is correct
2 Correct 19 ms 35452 KB Output is correct
3 Correct 22 ms 35476 KB Output is correct
4 Correct 19 ms 35456 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 18 ms 35480 KB Output is correct
7 Correct 22 ms 35620 KB Output is correct
8 Correct 20 ms 35412 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 19 ms 35668 KB Output is correct
11 Incorrect 19 ms 35540 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35524 KB Output is correct
2 Correct 19 ms 35452 KB Output is correct
3 Correct 22 ms 35476 KB Output is correct
4 Correct 19 ms 35456 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 18 ms 35480 KB Output is correct
7 Correct 22 ms 35620 KB Output is correct
8 Correct 20 ms 35412 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 19 ms 35668 KB Output is correct
11 Incorrect 19 ms 35540 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 48428 KB Output is correct
2 Correct 42 ms 48340 KB Output is correct
3 Correct 71 ms 50892 KB Output is correct
4 Correct 71 ms 51008 KB Output is correct
5 Correct 126 ms 55640 KB Output is correct
6 Correct 113 ms 54860 KB Output is correct
7 Correct 133 ms 55380 KB Output is correct
8 Correct 141 ms 55420 KB Output is correct
9 Correct 129 ms 59900 KB Output is correct
10 Incorrect 100 ms 48468 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36359530063629'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 54380 KB Output is correct
2 Correct 102 ms 59116 KB Output is correct
3 Correct 47 ms 48332 KB Output is correct
4 Correct 40 ms 48340 KB Output is correct
5 Correct 267 ms 89392 KB Output is correct
6 Correct 418 ms 87756 KB Output is correct
7 Correct 19 ms 35412 KB Output is correct
8 Correct 164 ms 63040 KB Output is correct
9 Correct 179 ms 67644 KB Output is correct
10 Correct 90 ms 55764 KB Output is correct
11 Correct 105 ms 59200 KB Output is correct
12 Correct 20 ms 35520 KB Output is correct
13 Correct 19 ms 35584 KB Output is correct
14 Correct 22 ms 35500 KB Output is correct
15 Correct 18 ms 35516 KB Output is correct
16 Correct 41 ms 48332 KB Output is correct
17 Correct 43 ms 48360 KB Output is correct
18 Correct 97 ms 57776 KB Output is correct
19 Correct 121 ms 61500 KB Output is correct
20 Correct 95 ms 56928 KB Output is correct
21 Correct 112 ms 57360 KB Output is correct
22 Correct 111 ms 56936 KB Output is correct
23 Correct 112 ms 59112 KB Output is correct
24 Correct 45 ms 48428 KB Output is correct
25 Correct 42 ms 48340 KB Output is correct
26 Correct 71 ms 50892 KB Output is correct
27 Correct 71 ms 51008 KB Output is correct
28 Correct 126 ms 55640 KB Output is correct
29 Correct 113 ms 54860 KB Output is correct
30 Correct 133 ms 55380 KB Output is correct
31 Correct 141 ms 55420 KB Output is correct
32 Correct 21 ms 35524 KB Output is correct
33 Correct 19 ms 35452 KB Output is correct
34 Correct 22 ms 35476 KB Output is correct
35 Correct 19 ms 35456 KB Output is correct
36 Correct 19 ms 35540 KB Output is correct
37 Correct 18 ms 35480 KB Output is correct
38 Correct 22 ms 35620 KB Output is correct
39 Correct 20 ms 35412 KB Output is correct
40 Correct 18 ms 35516 KB Output is correct
41 Correct 19 ms 35668 KB Output is correct
42 Incorrect 19 ms 35540 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
43 Halted 0 ms 0 KB -