Submission #1289908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289908		MMihalev	Catfish Farm (IOI22_fish)	C++20	3 / 100	77 ms	17504 KiB

fish

#include<iostream>
#include<algorithm>
#include<vector>
#include "fish.h"
using namespace std;
const int MAX_N=1e5+5;
int n,m;
vector<int>x,y,w;
vector<pair<int,int>>cells[MAX_N];//rows,weight
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W)
{
    n=N;
    m=M;
    x=X;
    y=Y;
    w=W;

    for(int i=0;i<m;i++)
    {
        cells[x[i]].push_back({y[i],w[i]});
    }
    for(int i=0;i<n;i++)
    {
        sort(cells[i].begin(),cells[i].end());
    }

    long long ans=0;

    long long ans0=0,ans1=0;
    for(int i=0;i<m;i++)
    {
        if(x[i]==0)ans0+=w[i];
        else ans1+=w[i];
    }
    ans-max(ans1,ans0);

    if(n==2)
    {
        return ans;
    }


    long long sum0=0,sum1=0;
    int id0=0,id1=0;
    for(int i=0;i<n;i++)
    {
        while(id0<cells[0].size() && cells[0][id0].first<=i)
        {
            sum0+=cells[0][id0].second;
            id0++;
        }
        while(id1<cells[1].size() && cells[1][id1].first<=i)
        {
            sum1+=cells[1][id1].second;
            id1++;
        }

        ans=max(ans,sum0+ans1-sum1);
    }

    return ans;
}

• Subtask 1: 3 / 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