Submission #1180826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180826		PagodePaiva	Catfish Farm (IOI22_fish)	C++20	0 / 100	41 ms	8296 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
#include <vector>
#define ll long long

using namespace std;

const int N = 3010;
const int LOGN = 20;

struct RMQ{
    ll rmq[N][LOGN];
    int lg[N];
    int n;
    void build(vector <ll> v){
        n = v.size();
        lg[1] = 0;
        for(int i = 2;i <= n;i++){
            lg[i] = lg[i/2]+1;
        }
        for(int i = 1;i <= n;i++)
            rmq[i][0] = v[i-1];
        for(int bit = 1;bit < LOGN;bit++){
            for(int i = 1;i <= n;i++){
                rmq[i][bit] = max(rmq[i][bit-1], rmq[min(n, i+(1<<(bit-1)))][bit-1]);
            }
        }
        return;
    }
    ll query(int l, int r){
        l++;
        r++;
        if(l > r) return -1e18;
        int t = (1<<lg[r-l+1]);
        return max(rmq[l][lg[r-l+1]], rmq[r-t+1][lg[r-l+1]]);
    }
} 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]);
            // cout << ant.back() << ' ';
        }
        // 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], dp[i-1][y][3]});
            // cout << rmq[0].query(0, y)+pref[y][0] << ' ' << rmq[1].query(y+1, n)-pref[y][1] << ' ' << dp[i-1][y][2] << ' ' << dp[i-1][y][3] << ' ' << dp[i][y][0] << '\n';
        }
        // 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: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16