제출 #1183323

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

fish

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<double>
using namespace std;
const int mxn=1e5+5;
vector<pii>g[mxn];
vector<pll>qr[mxn];
long long max_weights(int N, int M,vi X,vi Y,vi W){
    for(int i=0;i<M;i++)g[X[i]].pb({Y[i],W[i]});
    for(int i=0;i<N;i++)sort(all(g[i]));
    for(int i=0;i<N;i++)for(int j=1;j<g[i].size();j++)g[i][j].s+=g[i][j-1].s;
    for(int i=0;i<M;i++){
        if(X[i]>0)qr[X[i]-1].pb({Y[i],0});
        if(X[i]<N)qr[X[i]+1].pb({Y[i],0});
    }for(int i=0;i<N;i++)qr[i].pb({0,0});
    for(int i=0;i<N;i++)sort(all(qr[i])),qr[i].erase(unique(all(qr[i])),qr[i].end());
    ll rs=0;
    for(int i=0;i<N;i++){
        if(i!=0){
            int idx=0,idx2=0,idx3=0;
            ll sm=0,sm2=0,mx=0;
            for(int j=0;j<qr[i].size();j++){
                while(idx<g[i-1].size()&&g[i-1][idx].f<=qr[i][j].f)sm=g[i-1][idx++].s;
                while(idx2<qr[i-1].size()&&qr[i-1][idx2].f<=qr[i][j].f){
                    while(idx3<g[i-1].size()&&g[i-1][idx3].f<=qr[i-1][idx2].f)sm2=g[i-1][idx3++].s;
                    mx=max(mx,qr[i-1][idx2].s-sm2);idx2++;
                }qr[i][j].s=max(qr[i][j].s,sm+mx);
            }idx=(int)g[i].size()-1,idx2=(int)qr[i-1].size()-1,idx3=(int)g[i].size()-1,sm=0,sm2=0,mx=0;
            if(idx>=0)sm=g[i][idx].s,sm2=g[i][idx3].s;
            for(int j=qr[i].size()-1;j>=0;j--){
                while(idx>=0&&g[i][idx].f>=qr[i][j].f)sm=g[i][idx--].s;
                while(idx2>=0&&qr[i-1][idx2].f>=qr[i][j].f){
                    while(idx3>=0&&g[i][idx3].f>=qr[i-1][idx2].f)sm2=g[i][idx3--].s;
                    mx=max(mx,qr[i-1][idx2].s+sm2);idx2--;
                }qr[i][j].s=max(qr[i][j].s,mx-sm);
            }
        }
        int idx=0;ll sm=0;
        for(int j=0;j<qr[i].size();j++){
            while(idx<g[i+1].size()&&g[i+1][idx].f<=qr[i][j].f)sm=g[i+1][idx++].s;
            rs=max(rs,sm+qr[i][j].s);
        }continue;
    }return rs;
}
/*int main(){
    cout<<max_weights(5, 4,{0, 1, 4, 3},{2, 1, 4, 3},{5, 2, 1, 3});
}*/

• 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