oj.uz

Submission #1078870

# Submission time Handle Problem Language Result Execution time Memory
1078870 2024-08-28T07:33:17 Z The_Samurai Catfish Farm (IOI22_fish) C++17
12 / 100
 1000 ms 52048 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 - 1].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 - 1].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 53 ms 25032 KB Output is correct
2 Correct 71 ms 28608 KB Output is correct
3 Correct 23 ms 22108 KB Output is correct
4 Correct 22 ms 22104 KB Output is correct
5 Correct 157 ms 48676 KB Output is correct
6 Correct 144 ms 52048 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1094 ms 25016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22364 KB Output is correct
2 Correct 22 ms 22104 KB Output is correct
3 Correct 44 ms 23856 KB Output is correct
4 Correct 36 ms 24664 KB Output is correct
5 Correct 58 ms 29268 KB Output is correct
6 Correct 61 ms 29336 KB Output is correct
7 Correct 71 ms 29164 KB Output is correct
8 Correct 58 ms 29216 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '276517851045'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '276517851045'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '276517851045'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22364 KB Output is correct
2 Correct 22 ms 22104 KB Output is correct
3 Correct 44 ms 23856 KB Output is correct
4 Correct 36 ms 24664 KB Output is correct
5 Correct 58 ms 29268 KB Output is correct
6 Correct 61 ms 29336 KB Output is correct
7 Correct 71 ms 29164 KB Output is correct
8 Correct 58 ms 29216 KB Output is correct
9 Correct 59 ms 29268 KB Output is correct
10 Correct 57 ms 21864 KB Output is correct
11 Correct 118 ms 47052 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 21 ms 22204 KB Output is correct
19 Correct 23 ms 22360 KB Output is correct
20 Correct 30 ms 22100 KB Output is correct
21 Correct 24 ms 22360 KB Output is correct
22 Incorrect 67 ms 33508 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '44681349514206'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25032 KB Output is correct
2 Correct 71 ms 28608 KB Output is correct
3 Correct 23 ms 22108 KB Output is correct
4 Correct 22 ms 22104 KB Output is correct
5 Correct 157 ms 48676 KB Output is correct
6 Correct 144 ms 52048 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1094 ms 25016 KB Time limit exceeded
9 Halted 0 ms 0 KB -