Submission #1290005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290005		MMihalev	메기 농장 (IOI22_fish)	C++20	35 / 100	1097 ms	53544 KiB

fish

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<tuple>
#include "fish.h"
using namespace std;
const int MAX_N=1e5+5;
int n,m;
vector<int>x,y,w;
vector<pair<int,long long>>cells[MAX_N];//rows,weight
long long tree[4][MAX_N][3][2];
long long all,up,down,all0,up0,down0,down1;
//col , j(could be -1!), mode,  pref/suf
vector<tuple<int,int,int>>updates[4];
void Update(int col,int pos,int mode,int prefsuf,long long val)
{
    if(val>0)updates[col].push_back({pos,mode,prefsuf});

    pos++;
    for(;;)
    {
        if(pos>n)break;
        tree[col][pos][mode][prefsuf]=max(tree[col][pos][mode][prefsuf],val);
        pos+=((pos)&(-pos));
    }
}
long long Find(int col,int pos,int mode,int prefsuf)
{
    long long res=0;
    pos++;
    for(;;)
    {
        if(pos<1)break;
        res=max(res,tree[col][pos][mode][prefsuf]);
        pos-=((pos)&(-pos));
    }
    return res;
}
long long query(int col,int j,int mode,int prefsuf)
{
    if(prefsuf==0)
    {
        return Find(col,j,mode,prefsuf);
    }

    j=n-1-j;

    return Find(col,j,mode,prefsuf);
}
void transition(int i,int j)
{
    if(j==-1)return;

    long long ans=0,ansup=0;
    up=all-down;
    up0=all0-down0;
    ans=down0;

    if(i-1>=0)
    {ans=max(ans,query(0,j,0,0)-up0);
    ansup=max(ansup,query(0,j,1,1)-down);}

    if(i-2>=0)
    {ans=max(ans,query(1,j,2,0)+down0);
    ans=max(ans,query(1,j,1,1));}

    if(i-3>=0)
    {ans=max(ans,query(2,n-1,1,0)+down0);}

    Update(3,j,0,0,ans+up);
    Update(3,n-1-j,0,1,ans+up);

    ans=max(ans,ansup);

    if(i+1<n)
    {Update(3,j,1,0,ans+down1);
    Update(3,n-1-j,1,1,ans+down1);}

    Update(3,j,2,0,ans);
    Update(3,n-1-j,2,1,ans);
}
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;

    for(int i=0;i<n;i++)
    {
        all=0;up=0;down=0;
        all0=0;up0=0;down0=0;
        down1=0;
        for(auto [row,price]:cells[i])all+=price;
        if(i-1>=0)for(auto [row,price]:cells[i-1])all0+=price;
        int id0=0;
        int id1=0;
        for(auto [row,price]:cells[i])
        {
            while(i-1>=0 && id0<cells[i-1].size() && cells[i-1][id0].first<row)
            {
                down0+=cells[i-1][id0].second;
                id0++;
            }
            while(i+1<n && id1<cells[i+1].size() && cells[i+1][id1].first<row)
            {
                down1+=cells[i+1][id1].second;
                id1++;
            }

            transition(i,row-1);

            while(i-1>=0 && id0<cells[i-1].size() && cells[i-1][id0].first<=row)
            {
                down0+=cells[i-1][id0].second;
                id0++;
            }
            while(i+1<n && id1<cells[i+1].size() && cells[i+1][id1].first<=row)
            {
                down1+=cells[i+1][id1].second;
                id1++;
            }
            down+=price;

            transition(i,row);
        }

        while(i-1>=0 && id0<cells[i-1].size() && cells[i-1][id0].first<=n-1)
        {
            down0+=cells[i-1][id0].second;
            id0++;
        }
        while(i+1<n && id1<cells[i+1].size() && cells[i+1][id1].first<=n-1)
        {
            down1+=cells[i+1][id1].second;
            id1++;
        }

        transition(i,n-1);


        swap(tree[3],tree[0]);
        swap(updates[3],updates[0]);
        swap(tree[3],tree[1]);
        swap(updates[3],updates[1]);
        swap(tree[3],tree[2]);
        swap(updates[3],updates[2]);

        for(auto [pos,mode,prefsuf]:updates[3])
        {
            Update(3,pos,mode,prefsuf,0);
        }
    }

    ans=max(ans,Find(0,n-1,2,0));
    ans=max(ans,Find(1,n-1,1,0));
    if(n>=3)ans=max(ans,Find(2,n-1,1,0));

    return ans;
}

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