Submission #832225

#	Time	Username	Problem	Language	Result	Execution time	Memory
832225		fatemetmhr	Catfish Farm (IOI22_fish)	C++17	9 / 100	158 ms	59900 KiB

fish

// 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 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16