Submission #773968

#	Time	Username	Problem	Language	Result	Execution time	Memory
773968		jasmin	Catfish Farm (IOI22_fish)	C++17	9 / 100	81 ms	41556 KiB

fish

#include "fish.h"
using namespace std;
#include<bits/stdc++.h>

#define ll long long


long long subtask1(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W){

    long long ans=0;
    for(int i=0; i<M; i++){
        ans+=W[i];
    }
    return ans;
}
long long subtask2(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W){
    
    vector<pair<int,int>> c0;
    vector<pair<int,int>> c1;
    long long sum0=0;
    long long sum1=0;
    for(int i=0; i<M; i++){

        if(X[i]==0){
            c0.push_back({Y[i], W[i]});
            sum0+=W[i];
        }
        else{
            c1.push_back({Y[i], W[i]});
            sum1+=W[i];
        }

    }
    
    if(N==2){
        return max(sum0, sum1);
    }

    sort(c1.begin(), c1.end());
    sort(c0.begin(), c0.end());
    long long ans=max(sum0, sum1);
    long long mom=sum1;
    int j=0;
    for(int i=0; i<(int)c1.size(); i++){

        while(j<(int)c0.size() && c0[j].first<c1[i].first){

            mom+=c0[j].second;
            j++;

        }

        ans=max(ans, mom);

        mom-=c1[i].second;
    }
    return ans;
}

long long gain(int h1, int free1, int h2, int free2, vector<pair<int,int> >& c1, vector<pair<int,int> >& c2){

    //wand von 1 ist grösser

    int wallh=c1[h1].first;

    ll ans=0;
    for(int i=(int)c2.size()-free2; i<(int)c2.size(); i++){
        
        if(c2[i].first < wallh){
            ans+= c2[i].second;
        }
    }
    return ans;

}

const int INF=1e9+7;
long long subtask3(int n, int m, vector<int> x, vector<int> y, vector<int> w){

    vector<vector<pair<int,int> > > c(n);
    for(int i=0; i<m; i++){

        c[x[i]].push_back({y[i], w[i]});

    }
    int maxh=0;
    for(int i=0; i<n; i++){
        sort(c[i].begin(), c[i].end());
        c[i].push_back({INF, 0});

        maxh=max(maxh, (int)c[i].size());
    }


    vector<vector<vector<ll> > > dp(n, vector<vector<ll> > (maxh, vector<ll> (maxh)));
    for(int i=1; i<n; i++){

        for(int h=0; h<maxh; h++){
            for(int free=0; free<(int)c[i].size()-h; free++){


                for(int h0=0; h0<maxh; h0++){
                    for(int free0=0; free0<(int)c[i-1].size()-h0; free++){

                        
                        ll g=0;
                        if(c[i][h].first>c[i-1][h0].first){

                            g = gain(h, free, h0, free0, c[i], c[i-1]);

                        }
                        else{

                            g = gain(h0, free0, h, free, c[i-1], c[i]);
                        }

                        dp[i][h][free] = max(dp[i][h][free], dp[i-1][h0][free0] + g);

                    }
                }


            }
        }

    }

    ll ans=0;
    for(int h=0; h<maxh; h++){
        for(int free=0; free<maxh; free++){

            ans=max(ans, dp[n-1][h][free]);
        }
    }
    return ans;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    if(N==1) return 0;

    bool sub1=true;
    bool sub2=true;
    for(int i=0; i<M; i++){

        if(X[i]%2==1){
            sub1=false;
        }
        if(X[i]>1){
            sub2=false;
        }

    }

    if(sub1){
        return subtask1(N, M, X, Y, W);
    }
    if(sub2){
        return subtask2(N, M, X, Y, W);
    }


    return subtask3(N, M, X, Y, W);
}

• 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