Submission #1009930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009930		snpmrnhlol	Ants and Sugar (JOI22_sugar)	C++17	6 / 100	140 ms	17340 KiB

sugar

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
const ll inf = 1e18;
array<ll,3> v[N];
vector <ll> pos;
ll cost[N][4];
ll dp[N][4];
ll n,k,sz;
ll sum = 0;
ll get(){
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;
    dp[0][3] = 0;
    for(ll i = 1;i < sz;i++){
        for(ll j = 0;j < 4;j++){
            dp[i][j] = -inf;
        }
        for(ll j = 0;j < 4;j++){
            if(j/2 == 0){
                dp[i][j] = max(dp[i][j],dp[i - 1][0] + cost[i][j]);
                dp[i][j] = max(dp[i][j],dp[i - 1][2] + cost[i][j]);
            }else{
                dp[i][j] = max(dp[i][j],dp[i - 1][1] + cost[i][j]);
                dp[i][j] = max(dp[i][j],dp[i - 1][3] + cost[i][j]);
            }
            //cout<<pos[i]<<' '<<cost[i][j]<<' '<<dp[i][j]<<' ';
        }
        //cout<<'\n';
    }
    return max(dp[sz - 1][0],dp[sz - 1][2]);
}
int main(){
    cin>>n>>k;
    for(ll i = 0;i < n;i++){
        cin>>v[i][0]>>v[i][1]>>v[i][2];
        pos.push_back(v[i][1]);
    }
    pos.push_back(-inf);
    pos.push_back(inf);
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    sz = pos.size();
    for(ll i = 0;i < n;i++){
        if(v[i][0] == 1){
            for(ll j = 0;j < sz;j++){
                if(pos[j] == v[i][1]){
                    cost[j][1]+=v[i][2];
                    cost[j][3]+=v[i][2];
                }
            }
            sum+=v[i][2];
        }else if(v[i][0] == 2){
            bool ok = 0;
            for(ll j = 0;j < sz;j++){
                if(v[i][1] - k <= pos[j] && pos[j] <= v[i][1] + k){
                    cost[j][1]-=v[i][2];
                    if(!ok){cost[j][3]-=v[i][2];ok = 1;}
                }
            }
        }
        cout<<sum - get()<<'\n';
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52