oj.uz

Submission #1078869

# Submission time Handle Problem Language Result Execution time Memory
1078869 2024-08-28T07:32:24 Z The_Samurai Catfish Farm (IOI22_fish) C++17
12 / 100
 170 ms 58708 KB 
#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vector<vector<pair<int, int>>> a(n);
    for (int i = 0; i < m; i++) a[X[i]].emplace_back(Y[i] + 1, W[i]);
    vector<vector<pair<int, ll>>> dp(n), dp2(n), pref(n);

    for (int x = 0; x < n; x++) {
        sort(a[x].begin(), a[x].end());
        a[x].emplace_back(n + 1, 0);
        ll sum = 0;
        for (auto [y, w]: a[x]) {
            sum += w;
            pref[x].emplace_back(y, sum);
        }
    }
    auto get = [&](int x, int l, int r) -> ll {
        if (l > r) return 0;
        int i = lower_bound(pref[x].begin(), pref[x].end(), make_pair(l, 0ll)) - pref[x].begin();
        int j = lower_bound(pref[x].begin(), pref[x].end(), make_pair(r + 1, 0ll)) - pref[x].begin() - 1;
        if (i > j) return 0;
        return pref[x][j].ss - (i > 0 ? pref[x][i - 1].ss : 0ll);
    };
    for (auto [y, w]: a[0]) dp[0].emplace_back(y - 1, 0);

    ll ans = 0;
    for (int x = 1; x < n; x++) {
        // cout << '\t' << x << endl;
        for (int i = 0; i < a[x].size(); i++) {
            a[x][i].ff--;
            ll mx = 0, mx2 = 0;
            for (int j = 0; j < a[x - 1].size(); j++) {
                if (dp[x - 1][j].ff <= a[x][i].ff) {
                    mx = max(mx, dp[x - 1][j].ss + get(x - 1, dp[x - 1][j].ff + 1, a[x][i].ff));
                    if (j < dp2[x - 1].size()) mx = max(mx, dp2[x - 1][j].ss);
                }
                if (dp[x - 1][j].ff >= a[x][i].ff) {
                    mx2 = max(mx2, dp[x - 1][j].ss + get(x, a[x][i].ff + 1, dp[x - 1][j].ff));
                    if (j < dp2[x].size()) mx2 = max(mx2, dp2[x - 1][j].ss + get(x, a[x][i].ff + 1, dp[x - 1][j].ff));

                }
            }
            dp[x].emplace_back(a[x][i].ff, mx);
            // cout << i << ' ' << a[x][i].ff << ' ' << dp[x].back().ss << endl;
            dp2[x].emplace_back(a[x][i].ff, mx2);
            ans = max(ans, max(mx, mx2));
            a[x][i].ff++;
        }
    }

    return ans;

    
}

// g++ -o fish -O2 fish.cpp grader.cpp -std=c++17 && .\fish < input.txt > output.txt

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i = 0; i < a[x].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j = 0; j < a[x - 1].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                     if (j < dp2[x - 1].size()) mx = max(mx, dp2[x - 1][j].ss);
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                     if (j < dp2[x].size()) mx2 = max(mx2, dp2[x - 1][j].ss + get(x, a[x][i].ff + 1, dp[x - 1][j].ff));
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 26572 KB Output is correct
2 Correct 55 ms 30148 KB Output is correct
3 Correct 29 ms 22360 KB Output is correct
4 Correct 27 ms 22324 KB Output is correct
5 Correct 162 ms 55076 KB Output is correct
6 Correct 170 ms 58708 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 22156 KB Output is correct
2 Correct 22 ms 22616 KB Output is correct
3 Correct 46 ms 24864 KB Output is correct
4 Correct 38 ms 25304 KB Output is correct
5 Correct 65 ms 30784 KB Output is correct
6 Correct 54 ms 30288 KB Output is correct
7 Correct 63 ms 30800 KB Output is correct
8 Correct 58 ms 30836 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 22156 KB Output is correct
2 Correct 22 ms 22616 KB Output is correct
3 Correct 46 ms 24864 KB Output is correct
4 Correct 38 ms 25304 KB Output is correct
5 Correct 65 ms 30784 KB Output is correct
6 Correct 54 ms 30288 KB Output is correct
7 Correct 63 ms 30800 KB Output is correct
8 Correct 58 ms 30836 KB Output is correct
9 Correct 66 ms 30544 KB Output is correct
10 Incorrect 52 ms 23788 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36364983059693'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 26572 KB Output is correct
2 Correct 55 ms 30148 KB Output is correct
3 Correct 29 ms 22360 KB Output is correct
4 Correct 27 ms 22324 KB Output is correct
5 Correct 162 ms 55076 KB Output is correct
6 Correct 170 ms 58708 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Runtime error 93 ms 50268 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -