oj.uz

Submission #994317

# Submission time Handle Problem Language Result Execution time Memory
994317 2024-06-07T10:53:30 Z thinknoexit Catfish Farm (IOI22_fish) C++17
26 / 100
 104 ms 36208 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<int, int>> pos[100100];
struct DP {
    ll in, de;
    DP() {
        in = de = 0;
    }
} dp[1001000];
int w[1001000];
int n, m;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N, m = M;
    for (int i = 0;i < m;i++) {
        w[i + 1] = W[i];
        pos[X[i] + 1].push_back({ Y[i] + 1, i + 1 });
    }
    int idx = m, p;
    ll mx, sum;
    for (int i = 2;i <= n;i++) {
        sort(pos[i].begin(), pos[i].end());
        pos[i].push_back({ 0, ++idx });
        pos[i].push_back({ n + 1, ++idx });
        sort(pos[i].begin(), pos[i].end());
        // in -> in
        {
            p = 0;
            mx = 0;
            for (int j = 0;j < (int)pos[i].size();j++) {
                while (p < (int)pos[i - 1].size() && pos[i - 1][p].first <= pos[i][j].first - 1) {
                    int prev = pos[i - 1][p++].second;
                    mx = max(mx, dp[prev].in) + w[prev];
                }
                if (p < (int)pos[i - 1].size() && pos[i - 1][p].first == pos[i][j].first) {
                    mx = max(mx, dp[pos[i - 1][p].second].in);
                }
                dp[pos[i][j].second].in = mx;
            }
        }
        // de -> de , in -> de
        {
            p = pos[i - 1].size() - 1;
            mx = 0;
            for (int j = pos[i].size() - 1;j >= 0;j--) {
                while (p >= 0 && pos[i - 1][p].first > pos[i][j].first) {
                    int prev = pos[i - 1][p--].second;
                    mx = max({ mx, dp[prev].in, dp[prev].de });
                }
                mx += w[pos[i][j].second];
                while (p >= 0 && pos[i - 1][p].first == pos[i][j].first) {
                    int prev = pos[i - 1][p--].second;
                    mx = max({ mx, dp[prev].in, dp[prev].de });
                }
                dp[pos[i][j].second].de = mx;
            }
        }
        // in -> de, de -> in
        if (i >= 3) {
            // h[i-2] <= h[i]
            {
                int mid = 0;
                p = 0;
                mx = 0, sum = 0;
                for (int j = 0;j < (int)pos[i].size();j++) {
                    while (p < (int)pos[i - 2].size() && pos[i - 2][p].first <= pos[i][j].first) {
                        int prev = pos[i - 2][p++].second;
                        mx = max({ mx ,dp[prev].in, dp[prev].de });
                    }
                    while (mid < (int)pos[i - 1].size() && pos[i - 1][mid].first <= pos[i][j].first - 1) {
                        sum += w[pos[i - 1][mid++].second];
                    }
                    dp[pos[i][j].second].in = max(dp[pos[i][j].second].in, mx + sum);
                }
            }
            // h[i-2] >= h[i]
            {
                int mid = pos[i - 1].size() - 1;
                mx = 0, sum = 0;
                for (int j = 0;j <= mid;j++) sum += w[pos[i - 1][j].second];
                p = pos[i - 2].size() - 1;
                for (int j = pos[i].size() - 1;j >= 0;j--) {
                    while (p >= 0 && pos[i - 2][p].first >= pos[i][j].first) {
                        int prev = pos[i - 2][p].second;
                        int now = pos[i - 2][p].first - 1;
                        while (mid >= 0 && pos[i - 1][mid].first > now) {
                            sum -= w[pos[i - 1][mid--].second];
                        }
                        mx = max({ mx, dp[prev].in + sum, dp[prev].de + sum });
                        p--;
                    }
                    dp[pos[i][j].second].in = max(dp[pos[i][j].second].in, mx);
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 1;i <= idx;i++) {
        ans = max(ans, dp[i].in);
        ans = max(ans, dp[i].de);
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27588 KB Output is correct
2 Correct 30 ms 28616 KB Output is correct
3 Correct 12 ms 23132 KB Output is correct
4 Correct 12 ms 23132 KB Output is correct
5 Correct 103 ms 34744 KB Output is correct
6 Correct 104 ms 36208 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20056 KB Output is correct
2 Incorrect 51 ms 30128 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23128 KB Output is correct
2 Correct 14 ms 23132 KB Output is correct
3 Correct 30 ms 27372 KB Output is correct
4 Correct 22 ms 24860 KB Output is correct
5 Correct 42 ms 30108 KB Output is correct
6 Correct 40 ms 30288 KB Output is correct
7 Correct 40 ms 30168 KB Output is correct
8 Correct 40 ms 30288 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20056 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 3 ms 20060 KB Output is correct
4 Correct 3 ms 20056 KB Output is correct
5 Correct 3 ms 20060 KB Output is correct
6 Correct 3 ms 20060 KB Output is correct
7 Correct 3 ms 20060 KB Output is correct
8 Correct 3 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 3 ms 20060 KB Output is correct
11 Correct 4 ms 20056 KB Output is correct
12 Correct 3 ms 20060 KB Output is correct
13 Correct 3 ms 20056 KB Output is correct
14 Incorrect 4 ms 20060 KB 1st lines differ - on the 1st token, expected: '360901324355', found: '360406343483'
15 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20056 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 3 ms 20060 KB Output is correct
4 Correct 3 ms 20056 KB Output is correct
5 Correct 3 ms 20060 KB Output is correct
6 Correct 3 ms 20060 KB Output is correct
7 Correct 3 ms 20060 KB Output is correct
8 Correct 3 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 3 ms 20060 KB Output is correct
11 Correct 4 ms 20056 KB Output is correct
12 Correct 3 ms 20060 KB Output is correct
13 Correct 3 ms 20056 KB Output is correct
14 Incorrect 4 ms 20060 KB 1st lines differ - on the 1st token, expected: '360901324355', found: '360406343483'
15 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20056 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 3 ms 20060 KB Output is correct
4 Correct 3 ms 20056 KB Output is correct
5 Correct 3 ms 20060 KB Output is correct
6 Correct 3 ms 20060 KB Output is correct
7 Correct 3 ms 20060 KB Output is correct
8 Correct 3 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 3 ms 20060 KB Output is correct
11 Correct 4 ms 20056 KB Output is correct
12 Correct 3 ms 20060 KB Output is correct
13 Correct 3 ms 20056 KB Output is correct
14 Incorrect 4 ms 20060 KB 1st lines differ - on the 1st token, expected: '360901324355', found: '360406343483'
15 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23128 KB Output is correct
2 Correct 14 ms 23132 KB Output is correct
3 Correct 30 ms 27372 KB Output is correct
4 Correct 22 ms 24860 KB Output is correct
5 Correct 42 ms 30108 KB Output is correct
6 Correct 40 ms 30288 KB Output is correct
7 Correct 40 ms 30168 KB Output is correct
8 Correct 40 ms 30288 KB Output is correct
9 Correct 45 ms 30292 KB Output is correct
10 Correct 35 ms 27472 KB Output is correct
11 Correct 65 ms 32596 KB Output is correct
12 Correct 3 ms 20144 KB Output is correct
13 Correct 5 ms 20060 KB Output is correct
14 Correct 3 ms 20056 KB Output is correct
15 Correct 3 ms 20060 KB Output is correct
16 Correct 3 ms 20116 KB Output is correct
17 Correct 3 ms 20060 KB Output is correct
18 Correct 12 ms 23212 KB Output is correct
19 Correct 13 ms 23284 KB Output is correct
20 Correct 13 ms 23212 KB Output is correct
21 Correct 14 ms 23132 KB Output is correct
22 Correct 42 ms 29376 KB Output is correct
23 Correct 72 ms 32596 KB Output is correct
24 Correct 69 ms 32596 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27588 KB Output is correct
2 Correct 30 ms 28616 KB Output is correct
3 Correct 12 ms 23132 KB Output is correct
4 Correct 12 ms 23132 KB Output is correct
5 Correct 103 ms 34744 KB Output is correct
6 Correct 104 ms 36208 KB Output is correct
7 Correct 3 ms 20056 KB Output is correct
8 Incorrect 51 ms 30128 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
9 Halted 0 ms 0 KB -