제출 #647166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647166		PoonYaPat	메기 농장 (IOI22_fish)	C++17	0 / 100	712 ms	270676 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

ll dp[300001],sl[300001],sr[300001],si[300001],mmax[100001],mmax_mi[100001],ans,ma;
map<pii,int> val;
vector<pii> vv,v,temp_val; //(index, height)
queue<pii> temp_col; //(height, index)
queue<pii> col[100001]; //(height, value)
set<int> cor_x;
queue<int> qx;
multiset<ll, greater<ll>> mo,le;

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i=0; i<m; ++i) {
        val[pii(X[i],Y[i])]=W[i];
        vv.push_back(pii(X[i],Y[i]));
        cor_x.insert(X[i]);
        if (X[i]) v.push_back(pii(X[i]-1,Y[i]));
        if (X[i]<n-1) v.push_back(pii(X[i]+1,Y[i]));
    }

    for (auto s : cor_x) qx.push(s);

    sort(vv.begin(),vv.end());
    for (auto s : vv) col[s.first].push(pii(s.second,val[pii(s.first,s.second)]));


    sort(v.begin(),v.end());

    int i=1,pre=-1;

    for (auto s : v) {
        int x=s.first, y=s.second;

        if (x==pre) { //same x_cor
            si[i]=si[i-1];
            while (!col[x].empty() & y>=col[x].front().first) {
                si[i]+=col[x].front().second;
                col[x].pop();
            }
            sr[i]=sr[i-1]+val[pii(x+1,y)];
            sl[i]=sl[i-1]+val[pii(x-1,y)];

        } else { //new x_cor
            while (!col[x].empty() & y>=col[x].front().first) {
                si[i]+=col[x].front().second;
                col[x].pop();
            }
            sr[i]=val[pii(x+1,y)];
            sl[i]=val[pii(x-1,y)];

            //clear more, less, temp
            mo.clear();
            le.clear();
            while (!temp_col.empty()) temp_col.pop();

            for (auto h : temp_val) {
                mo.insert(dp[h.first]);
                temp_col.push(pii(h.second,h.first));
            }
            temp_val.clear();

            //find max from all previous col (ma)
            while (!qx.empty() && qx.front()<x-2) {
                ma=max(ma,mmax[qx.front()]);
                qx.pop();
            }
            if (qx.front()==x-2) ma=max(ma,mmax_mi[qx.front()]);
        }

        //more to less
        while (!temp_col.empty() && temp_col.front().first<y) {
            int idx=temp_col.front().second;
            temp_col.pop();

            auto it=mo.find(dp[idx]);
            mo.erase(it);
            le.insert(dp[idx]-si[idx]-sr[idx]);
        }

        dp[i]=ma+sl[i]+sr[i];

        if (!mo.empty()) dp[i]=max(dp[i],*(mo.begin())-si[i]+sr[i]);
        if (!le.empty()) dp[i]=max(dp[i],*(le.begin())+sl[i]+sr[i]);

        mmax_mi[x]=max(mmax_mi[x],dp[i]-sr[i]);
        mmax[x]=max(mmax[x],dp[i]);

        ans=max(ans,dp[i]);
        temp_val.push_back(pii(i,y));

        ++i;
        if (x!=pre) pre=x;
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   40 |             while (!col[x].empty() & y>=col[x].front().first) {
      |                                      ~^~~~~~~~~~~~~~~~~~~~~~
fish.cpp:48:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   48 |             while (!col[x].empty() & y>=col[x].front().first) {
      |                                      ~^~~~~~~~~~~~~~~~~~~~~~

• 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