oj.uz

Submission #832225

# Submission time Handle Problem Language Result Execution time Memory
832225 2023-08-21T07:08:41 Z fatemetmhr Catfish Farm (IOI22_fish) C++17
9 / 100
 158 ms 59900 KB 
// komak!

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const ll mod   = 1e9 + 7;
const int maxn5 = 3e5 + 10;

vector <pair<int, ll>> av[maxn5];
vector <ll> ps[maxn5], dp[maxn5][2];

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {

    for(int i = 0; i < m; i++){
        av[x[i]].pb({y[i], w[i]});
    }
    for(int i = 0; i < n; i++){
        av[i].pb({n, 0});
        sort(all(av[i]));
        ps[i].resize(int(av[i].size()));
        ps[i][0] = av[i][0].se;
        for(int j = 1; j < int(av[i].size()); j++){
            ps[i][j] = ps[i][j - 1] + av[i][j].se;
        }
        dp[i][0].resize(int(av[i].size()));
        dp[i][1].resize(int(av[i].size()));
    }

    ll ans = 0;

    for(int i = 0; i < int(av[0].size()); i++){
        dp[0][0][i] = (i ? -ps[0][i - 1] : 0);
        int pt = upper_bound(all(av[1]), mp(av[0][i].fi - 1, mod)) - av[1].begin() - 1;
        dp[0][1][i] = (pt >= 0 ? ps[1][pt] : 0);
        if(i)
            dp[0][0][i] = max(dp[0][0][i - 1], dp[0][0][i]);
    }

    for(int i = int(av[0].size()) - 2; i >= 0; i--)
        dp[0][1][i] = max(dp[0][1][i], dp[0][1][i + 1]);


    for(int i = 1; i < n; i++){
        ll keepmx = ans;
        for(int j = 0; j < int(av[i].size()); j++){
            int pt = upper_bound(all(av[i - 1]), mp(av[i][j].fi - 1, mod)) - av[i - 1].begin() - 1;
            dp[i][0][j] = keepmx;
            if(pt >= 0)
                dp[i][0][j] = max(dp[i][0][j], dp[i - 1][0][pt] + ps[i - 1][pt]);
            ans = max(ans, dp[i][0][j]);
            dp[i][0][j] += (j ? -ps[i][j - 1] : 0);
            if(j)
                dp[i][0][j] = max(dp[i][0][j - 1], dp[i][0][j]);
            dp[i][1][j] = keepmx;
            pt = upper_bound(all(av[i - 1]), mp(av[i][j].fi, mod)) - av[i - 1].begin();
            if(pt < int(av[i - 1].size()))
                dp[i][1][j] = max(dp[i][1][j], dp[i - 1][1][pt] - (j ? ps[i][j - 1] : 0));
            ans = max(ans, dp[i][1][j]);
            if(i < n - 1){
                pt = upper_bound(all(av[i + 1]), mp(av[i][j].fi - 1, mod)) - av[i + 1].begin() - 1;
                dp[i][1][j] = (pt >= 0 ? ps[i + 1][pt] : 0);
            }
        }
        for(int j = int(av[i].size()) - 2; j >= 0; j--)
            dp[i][1][j] = max(dp[i][1][j], dp[i][1][j + 1]);
    }

    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 44732 KB Output is correct
2 Correct 68 ms 47268 KB Output is correct
3 Correct 31 ms 40896 KB Output is correct
4 Correct 31 ms 40916 KB Output is correct
5 Correct 135 ms 59728 KB Output is correct
6 Correct 158 ms 59900 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28472 KB Output is correct
2 Correct 95 ms 49876 KB Output is correct
3 Correct 113 ms 53472 KB Output is correct
4 Correct 58 ms 44776 KB Output is correct
5 Correct 67 ms 47168 KB Output is correct
6 Correct 13 ms 28372 KB Output is correct
7 Correct 13 ms 28372 KB Output is correct
8 Correct 13 ms 28392 KB Output is correct
9 Correct 13 ms 28372 KB Output is correct
10 Correct 31 ms 40912 KB Output is correct
11 Correct 33 ms 40988 KB Output is correct
12 Correct 63 ms 44780 KB Output is correct
13 Correct 68 ms 47184 KB Output is correct
14 Correct 58 ms 44796 KB Output is correct
15 Correct 68 ms 46564 KB Output is correct
16 Correct 68 ms 44776 KB Output is correct
17 Correct 66 ms 46536 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 40916 KB Output is correct
2 Correct 34 ms 40984 KB Output is correct
3 Incorrect 48 ms 41784 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 13 ms 28372 KB Output is correct
3 Correct 13 ms 28480 KB Output is correct
4 Correct 12 ms 28460 KB Output is correct
5 Correct 12 ms 28372 KB Output is correct
6 Correct 12 ms 28468 KB Output is correct
7 Correct 12 ms 28372 KB Output is correct
8 Incorrect 12 ms 28372 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 13 ms 28372 KB Output is correct
3 Correct 13 ms 28480 KB Output is correct
4 Correct 12 ms 28460 KB Output is correct
5 Correct 12 ms 28372 KB Output is correct
6 Correct 12 ms 28468 KB Output is correct
7 Correct 12 ms 28372 KB Output is correct
8 Incorrect 12 ms 28372 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 13 ms 28372 KB Output is correct
3 Correct 13 ms 28480 KB Output is correct
4 Correct 12 ms 28460 KB Output is correct
5 Correct 12 ms 28372 KB Output is correct
6 Correct 12 ms 28468 KB Output is correct
7 Correct 12 ms 28372 KB Output is correct
8 Incorrect 12 ms 28372 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 40916 KB Output is correct
2 Correct 34 ms 40984 KB Output is correct
3 Incorrect 48 ms 41784 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 44732 KB Output is correct
2 Correct 68 ms 47268 KB Output is correct
3 Correct 31 ms 40896 KB Output is correct
4 Correct 31 ms 40916 KB Output is correct
5 Correct 135 ms 59728 KB Output is correct
6 Correct 158 ms 59900 KB Output is correct
7 Correct 12 ms 28472 KB Output is correct
8 Correct 95 ms 49876 KB Output is correct
9 Correct 113 ms 53472 KB Output is correct
10 Correct 58 ms 44776 KB Output is correct
11 Correct 67 ms 47168 KB Output is correct
12 Correct 13 ms 28372 KB Output is correct
13 Correct 13 ms 28372 KB Output is correct
14 Correct 13 ms 28392 KB Output is correct
15 Correct 13 ms 28372 KB Output is correct
16 Correct 31 ms 40912 KB Output is correct
17 Correct 33 ms 40988 KB Output is correct
18 Correct 63 ms 44780 KB Output is correct
19 Correct 68 ms 47184 KB Output is correct
20 Correct 58 ms 44796 KB Output is correct
21 Correct 68 ms 46564 KB Output is correct
22 Correct 68 ms 44776 KB Output is correct
23 Correct 66 ms 46536 KB Output is correct
24 Correct 32 ms 40916 KB Output is correct
25 Correct 34 ms 40984 KB Output is correct
26 Incorrect 48 ms 41784 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
27 Halted 0 ms 0 KB -