oj.uz

Submission #994316

# Submission time Handle Problem Language Result Execution time Memory
994316 2024-06-07T10:49:19 Z thinknoexit Catfish Farm (IOI22_fish) C++17
26 / 100
 102 ms 36684 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];
                }
                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 27600 KB Output is correct
2 Correct 31 ms 28620 KB Output is correct
3 Correct 12 ms 23132 KB Output is correct
4 Correct 12 ms 23132 KB Output is correct
5 Correct 102 ms 34784 KB Output is correct
6 Correct 97 ms 36204 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Incorrect 49 ms 30148 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 14 ms 23128 KB Output is correct
2 Correct 12 ms 23132 KB Output is correct
3 Correct 25 ms 27480 KB Output is correct
4 Correct 24 ms 25436 KB Output is correct
5 Correct 45 ms 31928 KB Output is correct
6 Correct 44 ms 31200 KB Output is correct
7 Correct 42 ms 31828 KB Output is correct
8 Correct 45 ms 31824 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20060 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 3 ms 20132 KB Output is correct
4 Correct 4 ms 20060 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 20128 KB Output is correct
9 Correct 3 ms 20060 KB Output is correct
10 Correct 4 ms 20316 KB Output is correct
11 Correct 3 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 3 ms 20136 KB Output is correct
14 Incorrect 3 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 20060 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 3 ms 20132 KB Output is correct
4 Correct 4 ms 20060 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 20128 KB Output is correct
9 Correct 3 ms 20060 KB Output is correct
10 Correct 4 ms 20316 KB Output is correct
11 Correct 3 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 3 ms 20136 KB Output is correct
14 Incorrect 3 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 20060 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 3 ms 20132 KB Output is correct
4 Correct 4 ms 20060 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 20128 KB Output is correct
9 Correct 3 ms 20060 KB Output is correct
10 Correct 4 ms 20316 KB Output is correct
11 Correct 3 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 3 ms 20136 KB Output is correct
14 Incorrect 3 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 14 ms 23128 KB Output is correct
2 Correct 12 ms 23132 KB Output is correct
3 Correct 25 ms 27480 KB Output is correct
4 Correct 24 ms 25436 KB Output is correct
5 Correct 45 ms 31928 KB Output is correct
6 Correct 44 ms 31200 KB Output is correct
7 Correct 42 ms 31828 KB Output is correct
8 Correct 45 ms 31824 KB Output is correct
9 Correct 41 ms 31636 KB Output is correct
10 Correct 44 ms 29100 KB Output is correct
11 Correct 74 ms 35920 KB Output is correct
12 Correct 3 ms 20060 KB Output is correct
13 Correct 3 ms 20060 KB Output is correct
14 Correct 3 ms 20060 KB Output is correct
15 Correct 3 ms 20056 KB Output is correct
16 Correct 3 ms 20060 KB Output is correct
17 Correct 3 ms 20148 KB Output is correct
18 Correct 12 ms 23132 KB Output is correct
19 Correct 12 ms 23064 KB Output is correct
20 Correct 13 ms 23128 KB Output is correct
21 Correct 12 ms 23132 KB Output is correct
22 Correct 46 ms 31376 KB Output is correct
23 Correct 69 ms 35920 KB Output is correct
24 Correct 76 ms 36684 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27600 KB Output is correct
2 Correct 31 ms 28620 KB Output is correct
3 Correct 12 ms 23132 KB Output is correct
4 Correct 12 ms 23132 KB Output is correct
5 Correct 102 ms 34784 KB Output is correct
6 Correct 97 ms 36204 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Incorrect 49 ms 30148 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
9 Halted 0 ms 0 KB -