Submission #993898

#	Time	Username	Problem	Language	Result	Execution time	Memory
993898		cpdreamer	Catfish Farm (IOI22_fish)	C++17	0 / 100	1066 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define V vector
#define pb push_back
struct segtree{
private:
    struct node{
        ll maxd;
    };
    node single(ll v){
        return {v};
    }
    node neutral={LLONG_MIN};
    node merge(node a,node b){
        return{max(a.maxd, b.maxd)};
    }
public:
    int size;
    V<node>query;
    void init(int n){
        size=1;
        while(size<n)size*=2;
        query.assign(2*size,neutral);
    }
    void build(V<ll>&a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<a.size()){
                query[x]=single(a[lx]);
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void build(V<ll>&a){
        build(a,0,0,size);
    }
    node calc(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l)
            return neutral;
        if(l<=lx && rx<=r)
            return query[x];
        int m=(lx+rx)/2;
        node a=calc(l,r,2*x+1,lx,m);
        node b=calc(l,r,2*x+2,m,rx);
        return merge(a,b);
    }
    long long calc(int l,int r){
        return calc(l,r,0,0,size).maxd;
    }
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
    vector<vector<long long >>grid(N+1,vector<long long>(N+1,0));
    for(int i=0;i<M;i++){
        grid[X[i]][Y[i]+1]+=W[i];
    }
    for(int i=0;i<N;i++){
        for(int j=1;j<=N;j++){
            grid[i][j]+=grid[i][j-1];
        }
    }
    V<V<V<ll>>>dp(N,V<V<ll>>(N+1,V<ll>(N+1,0)));
    V<V<V<ll>>>vp(N,V<V<ll>>(N+1,V<ll>(N+1,0)));
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            dp[0][i][j]=max(0LL,grid[0][j]-grid[0][i]);
            vp[0][i][j]=dp[0][i][j]+max(0LL,grid[1][i]-grid[1][j]);
        }
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<=N;j++){
            V<ll>a;
            for(int g=0;g<=N;g++)
                a.pb(dp[i-1][g][j]);
            segtree tree_dp;
            tree_dp.init(N+1);
            tree_dp.build(a);
            V<ll>b;
            for(int g=0;g<=N;g++)
                b.pb(vp[i-1][g][j]);
            segtree tree_vp;
            tree_vp.init(N+1);
            tree_vp.build(b);
            for(int g=0;g<=N;g++){
                if(g<=j){
                    dp[i][j][g]=tree_vp.calc(0,N+1);
                }
                else{
                    dp[i][j][g]=max(tree_dp.calc(0,g+1)+grid[i][g]-grid[i][j],tree_vp.calc(g,N+1));
                }
                vp[i][j][g]=dp[i][j][g]+max(0LL,grid[i+1][j]-grid[i+1][g]);
            }
        }
    }
    ll ans=LLONG_MIN;
    for(int i=0;i<=N;i++){
        ans=max(ans,dp[N-1][i][0]);
    }
    return ans;
}

Compilation message (stderr)

fish.cpp: In member function 'void segtree::build(std::vector<long long int>&, int, int, int)':
fish.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             if(lx<a.size()){
      |                ~~^~~~~~~~~

• 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