Submission #626874

#	Time	Username	Problem	Language	Result	Execution time	Memory
626874		ionan6ix	Catfish Farm (IOI22_fish)	C++17	18 / 100	81 ms	10048 KiB

fish

#include "fish.h"

#include <vector>
#include<algorithm>
using namespace std;

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

    bool flag = true;

    for(auto it:X)
        if(it%2)
        {
            flag = false;
            break;
        }

    if(flag)
    {
        long long sol = 0;
        for(auto it:W)
            sol+=it;

        return sol;
    }

    flag = true;

    for(auto it:X)
        if(it>1)
        {
            flag = false;
            break;
        }

    if(flag)
    {
        std::vector<pair<int,int> > y0;
        std::vector<pair<int,int> > y1;

        int sz = X.size();

        for(int i=0;i<M;i++)
            if(X[i]==0) y0.emplace_back(Y[i],W[i]);
            else y1.emplace_back(Y[i],W[i]);

        std::sort(y0.begin(),y0.end());
        std::sort(y1.begin(),y1.end());

        if(N==2)
        {
            //efectiv...

            long long sum0=0LL;
            long long sum1=0LL;

            for(auto it:y0)
                sum0+=1LL*it.second;

            for(auto it:y1)
                sum1+=1LL*it.second;

            return max(sum0,sum1);
        }
        long long sol = 0LL;
        long long sum = 0LL;

        for(auto it:y1)
            sum += 1LL*it.second;

        sol = sum;

        /**
         * Pana la un anumit punct luam din 0, apoi din 1
         */

        int pnt0 = -1;
        int pnt1 = 0;
        long long sum0 = 0;
        for(int i=0;i<(int)y0.size();i++)
        {
            pnt0++;
            sum0 += 1LL * y0[i].second;

            while(pnt1<(int)y1.size() && y1[pnt1].first<=y0[i].first)
            {
                sum -= 1LL * y1[pnt1].second;
                pnt1++;
            }
            sol = max(sol,sum+sum0);
        }
        sol = max(sol,sum+sum0);
        sum0 = 0LL;
        for(auto it:y0)
            sum0+=1LL*it.second;

        sol = max(sol,sum0);


        return sol;
    }

    flag = true;

    for(auto it:Y)
        if(it!=0)
        {
            flag = false;
            break;
        }

    if(flag)
    {

        vector<vector<long long> > dp;

        dp.resize(N+5);

        for(int i = 0;i<N;i++)
            dp[i].resize(4);



        vector<int> repr;
        repr.resize(N+5);

        for(int i = 0;i<M;i++)
            repr[X[i]] = W[i];

        dp[1][0] = 0;
        dp[1][1] = repr[0];
        dp[1][2] = repr[1];
        dp[1][3] = 0;

        for(int i=2;i<N;i++)
        {
            dp[i][0] = max(max(dp[i-2][0],dp[i-2][2]),max(dp[i-2][1],dp[i-2][3])+1LL*repr[i-1]);
            dp[i][1] = max(max(dp[i-2][0],dp[i-2][2])+1LL*repr[i-1],max(dp[i-2][1],dp[i-2][3])+1LL*repr[i-1]);
            dp[i][2] = max(max(dp[i-2][0]+1LL*repr[i-2]+1LL*repr[i],dp[i-2][2]+1LL*repr[i]),max(dp[i-2][1]+1LL*repr[i],dp[i-2][3]+1LL*repr[i]));
            dp[i][3] = max(max(dp[i-2][0]+1LL*repr[i-2],dp[i-2][2]),max(dp[i-2][1],dp[i-2][3]));
        }
        return max(max(dp[N-1][0],dp[N-1][1]),max(dp[N-1][2],dp[N-1][3]));
    }
    return 0;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:42:13: warning: unused variable 'sz' [-Wunused-variable]
   42 |         int sz = X.size();
      |             ^~

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