oj.uz

Submission #832235

# Submission time Handle Problem Language Result Execution time Memory
832235 2023-08-21T07:19:33 Z fatemetmhr Catfish Farm (IOI22_fish) C++17
9 / 100
 173 ms 66668 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++){
            //debug(i);
            //debug(j);
            //debug(av[i][j].fi);
            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]);
            //debug(dp[i][0][j]);
            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())){
                //debug(dp[i - 1][1][pt]);

                dp[i][1][j] = max(dp[i][1][j], dp[i - 1][1][pt] - (j ? ps[i][j - 1] : 0));
            }
            //debug(dp[i][1][j]);
            //debug(pt);
            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);
                //debug(pt);


            }
        }
        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 61 ms 46204 KB Output is correct
2 Correct 70 ms 48956 KB Output is correct
3 Correct 35 ms 41012 KB Output is correct
4 Correct 38 ms 40892 KB Output is correct
5 Correct 143 ms 66116 KB Output is correct
6 Correct 173 ms 66668 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 99 ms 52636 KB Output is correct
3 Correct 116 ms 56956 KB Output is correct
4 Correct 63 ms 46192 KB Output is correct
5 Correct 67 ms 49000 KB Output is correct
6 Correct 15 ms 28476 KB Output is correct
7 Correct 13 ms 28492 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 12 ms 28460 KB Output is correct
10 Correct 35 ms 40876 KB Output is correct
11 Correct 33 ms 40992 KB Output is correct
12 Correct 73 ms 46132 KB Output is correct
13 Correct 69 ms 48948 KB Output is correct
14 Correct 63 ms 46168 KB Output is correct
15 Correct 73 ms 48260 KB Output is correct
16 Correct 62 ms 46156 KB Output is correct
17 Correct 79 ms 48180 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 40908 KB Output is correct
2 Correct 34 ms 40912 KB Output is correct
3 Incorrect 60 ms 42760 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '19227425297844'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28424 KB Output is correct
2 Correct 14 ms 28464 KB Output is correct
3 Correct 18 ms 28472 KB Output is correct
4 Correct 14 ms 28372 KB Output is correct
5 Correct 14 ms 28372 KB Output is correct
6 Correct 15 ms 28484 KB Output is correct
7 Correct 17 ms 28416 KB Output is correct
8 Correct 14 ms 28392 KB Output is correct
9 Incorrect 14 ms 28492 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '180180661865'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28424 KB Output is correct
2 Correct 14 ms 28464 KB Output is correct
3 Correct 18 ms 28472 KB Output is correct
4 Correct 14 ms 28372 KB Output is correct
5 Correct 14 ms 28372 KB Output is correct
6 Correct 15 ms 28484 KB Output is correct
7 Correct 17 ms 28416 KB Output is correct
8 Correct 14 ms 28392 KB Output is correct
9 Incorrect 14 ms 28492 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '180180661865'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28424 KB Output is correct
2 Correct 14 ms 28464 KB Output is correct
3 Correct 18 ms 28472 KB Output is correct
4 Correct 14 ms 28372 KB Output is correct
5 Correct 14 ms 28372 KB Output is correct
6 Correct 15 ms 28484 KB Output is correct
7 Correct 17 ms 28416 KB Output is correct
8 Correct 14 ms 28392 KB Output is correct
9 Incorrect 14 ms 28492 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '180180661865'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 40908 KB Output is correct
2 Correct 34 ms 40912 KB Output is correct
3 Incorrect 60 ms 42760 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '19227425297844'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 46204 KB Output is correct
2 Correct 70 ms 48956 KB Output is correct
3 Correct 35 ms 41012 KB Output is correct
4 Correct 38 ms 40892 KB Output is correct
5 Correct 143 ms 66116 KB Output is correct
6 Correct 173 ms 66668 KB Output is correct
7 Correct 13 ms 28372 KB Output is correct
8 Correct 99 ms 52636 KB Output is correct
9 Correct 116 ms 56956 KB Output is correct
10 Correct 63 ms 46192 KB Output is correct
11 Correct 67 ms 49000 KB Output is correct
12 Correct 15 ms 28476 KB Output is correct
13 Correct 13 ms 28492 KB Output is correct
14 Correct 13 ms 28372 KB Output is correct
15 Correct 12 ms 28460 KB Output is correct
16 Correct 35 ms 40876 KB Output is correct
17 Correct 33 ms 40992 KB Output is correct
18 Correct 73 ms 46132 KB Output is correct
19 Correct 69 ms 48948 KB Output is correct
20 Correct 63 ms 46168 KB Output is correct
21 Correct 73 ms 48260 KB Output is correct
22 Correct 62 ms 46156 KB Output is correct
23 Correct 79 ms 48180 KB Output is correct
24 Correct 37 ms 40908 KB Output is correct
25 Correct 34 ms 40912 KB Output is correct
26 Incorrect 60 ms 42760 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '19227425297844'
27 Halted 0 ms 0 KB -