oj.uz

Submission #832218

# Submission time Handle Problem Language Result Execution time Memory
832218 2023-08-21T06:58:14 Z fatemetmhr Catfish Farm (IOI22_fish) C++17
9 / 100
 160 ms 60152 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 = lower_bound(all(av[i - 1]), mp(av[i][j].fi, -1ll)) - 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 59 ms 44956 KB Output is correct
2 Correct 76 ms 47548 KB Output is correct
3 Correct 34 ms 41012 KB Output is correct
4 Correct 34 ms 40996 KB Output is correct
5 Correct 148 ms 59948 KB Output is correct
6 Correct 160 ms 60152 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28480 KB Output is correct
2 Correct 104 ms 50260 KB Output is correct
3 Correct 119 ms 53804 KB Output is correct
4 Correct 60 ms 45012 KB Output is correct
5 Correct 70 ms 47508 KB Output is correct
6 Correct 14 ms 28372 KB Output is correct
7 Correct 14 ms 28488 KB Output is correct
8 Correct 14 ms 28488 KB Output is correct
9 Correct 15 ms 28372 KB Output is correct
10 Correct 35 ms 40904 KB Output is correct
11 Correct 33 ms 40908 KB Output is correct
12 Correct 61 ms 45104 KB Output is correct
13 Correct 69 ms 47408 KB Output is correct
14 Correct 63 ms 45012 KB Output is correct
15 Correct 73 ms 46920 KB Output is correct
16 Correct 70 ms 45044 KB Output is correct
17 Correct 72 ms 46792 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40992 KB Output is correct
2 Correct 33 ms 40984 KB Output is correct
3 Incorrect 50 ms 42076 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 15 ms 28480 KB Output is correct
2 Correct 14 ms 28480 KB Output is correct
3 Correct 14 ms 28432 KB Output is correct
4 Correct 14 ms 28388 KB Output is correct
5 Correct 14 ms 28428 KB Output is correct
6 Correct 14 ms 28372 KB Output is correct
7 Correct 14 ms 28372 KB Output is correct
8 Incorrect 14 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 15 ms 28480 KB Output is correct
2 Correct 14 ms 28480 KB Output is correct
3 Correct 14 ms 28432 KB Output is correct
4 Correct 14 ms 28388 KB Output is correct
5 Correct 14 ms 28428 KB Output is correct
6 Correct 14 ms 28372 KB Output is correct
7 Correct 14 ms 28372 KB Output is correct
8 Incorrect 14 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 15 ms 28480 KB Output is correct
2 Correct 14 ms 28480 KB Output is correct
3 Correct 14 ms 28432 KB Output is correct
4 Correct 14 ms 28388 KB Output is correct
5 Correct 14 ms 28428 KB Output is correct
6 Correct 14 ms 28372 KB Output is correct
7 Correct 14 ms 28372 KB Output is correct
8 Incorrect 14 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 33 ms 40992 KB Output is correct
2 Correct 33 ms 40984 KB Output is correct
3 Incorrect 50 ms 42076 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 59 ms 44956 KB Output is correct
2 Correct 76 ms 47548 KB Output is correct
3 Correct 34 ms 41012 KB Output is correct
4 Correct 34 ms 40996 KB Output is correct
5 Correct 148 ms 59948 KB Output is correct
6 Correct 160 ms 60152 KB Output is correct
7 Correct 17 ms 28480 KB Output is correct
8 Correct 104 ms 50260 KB Output is correct
9 Correct 119 ms 53804 KB Output is correct
10 Correct 60 ms 45012 KB Output is correct
11 Correct 70 ms 47508 KB Output is correct
12 Correct 14 ms 28372 KB Output is correct
13 Correct 14 ms 28488 KB Output is correct
14 Correct 14 ms 28488 KB Output is correct
15 Correct 15 ms 28372 KB Output is correct
16 Correct 35 ms 40904 KB Output is correct
17 Correct 33 ms 40908 KB Output is correct
18 Correct 61 ms 45104 KB Output is correct
19 Correct 69 ms 47408 KB Output is correct
20 Correct 63 ms 45012 KB Output is correct
21 Correct 73 ms 46920 KB Output is correct
22 Correct 70 ms 45044 KB Output is correct
23 Correct 72 ms 46792 KB Output is correct
24 Correct 33 ms 40992 KB Output is correct
25 Correct 33 ms 40984 KB Output is correct
26 Incorrect 50 ms 42076 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
27 Halted 0 ms 0 KB -