Submission #1181290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181290		PagodePaiva	Catfish Farm (IOI22_fish)	C++20	52 / 100	460 ms	298852 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
#include <vector>
#pragma GCC optimize("O3")

#define ll long long

using namespace std;

const int N = 3010;
const int LOGN = 12;

struct RMQ{
    ll pref[N], suf[N];
    int n;
    void build(vector <ll> &v){
        n = v.size();
        pref[0] = -1e18;
        for(int i = 1;i <= n;i++){
            pref[i] = max(pref[i-1], v[i-1]);
        }
        suf[n+1] = -1e18;
        for(int i = n;i > 0;i--){
            suf[i] = max(suf[i+1], v[i-1]);
        }
        return;
    }
    ll query(int l, int r){
        l++;
        r++;
        if(l > r) return -1e18;
        if(l == 0) return pref[r];
        return suf[l];
    }
} rmq[2];

ll dp[N][N][4];
vector <pair <int, ll>> x[N];
int n, m;
ll pref[N][2];
long long max_weights(int NN, int MM, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n = NN;
    m = MM;
    for(int i = 0;i < m;i++){
        x[X[i]+1].push_back({Y[i]+1, W[i]});
    }
    for(int i = 0;i < N;i++){
        sort(x[i].begin(), x[i].end());
    }
    for(int i = 1;i <= n;i++){
        //cout << i << '\n';
        vector <ll> ant;
        for(int j = 1, l = 0;j <= n;j++){
            pref[j][0] = pref[j-1][0];
            if(l != x[i].size()){
                if(x[i][l].first == j){
                    pref[j][0] += x[i][l].second;
                    l++;
                }
            }
        }
        for(int j = 1, l = 0;j <= n;j++){
            pref[j][1] = pref[j-1][1];
            if(l != x[i+1].size()){
                if(x[i+1][l].first == j){
                    pref[j][1] += x[i+1][l].second;
                    l++;
                }
            }
        }
        for(int y = 0;y <= n;y++){
            ant.push_back(dp[i-1][y][1]-pref[y][0]);
            //if(i == 3) //cout << ant.back() << ' ';
        }
        //if(i == 3) //cout << '\n';
        //// //cout << '\n';
        rmq[0].build(ant);
        ant.clear();
        for(int y = 0;y <= n;y++){
            ant.push_back(max({dp[i-1][y][0]+pref[y][1]}));
            // //cout << pref[y][1] << ' ';
        }
        // //cout << '\n';
   
        rmq[1].build(ant);
        // //cout << rmq[1].query(1, n) << ' ' << rmq[1].query(2, n) << '\n';
        // //cout << pref[0][1] << ' ' << pref[1][1] << '\n';
        for(int y = 0;y <= n;y++){
            dp[i][y][0] = max({rmq[0].query(0, y)+pref[y][0], rmq[1].query(y+1, n)-pref[y][1], dp[i-1][y][2] + pref[y][0], dp[i-1][y][3] + pref[y][0]});
            //cout << dp[i][y][0] << ' ';
        }
        //cout << '\n';
        ant.clear();
        for(int y = 0;y <= n;y++){
            ant.push_back(dp[i-1][y][1] -pref[y][0]);
            ////// //cout << ant.back() << ' ';
        }
       // //// //cout << '\n';
        rmq[0].build(ant);
        for(int y = 0;y <= n;y++){
            dp[i][y][1] = max({rmq[0].query(0, y)+pref[y][0], dp[i-1][y][2], dp[i-1][y][3]});
            //cout << dp[i][y][1] << ' ';
        }
        //cout << '\n';
        ant.clear();
        for(int y = 0;y <= n;y++){
            ant.push_back(dp[i-1][y][0]);
        }
        rmq[0].build(ant);
        for(int y = 0;y <= n;y++){
            dp[i][y][2] = rmq[0].query(0, y);
            //cout << dp[i][y][2] << ' ';
        }
        //cout << '\n';
        ant.clear();
        for(int y = 0;y <= n;y++){
            ant.push_back(dp[i-1][y][0]+pref[y][1]);
        }
        rmq[0].build(ant);
        for(int y = 0;y <= n;y++){
            dp[i][y][3] = rmq[0].query(y, n)- pref[y][1];
            //cout << dp[i][y][3] << ' ';
        }
        //cout << '\n';
    }
    return dp[n][0][0];
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16