Submission #1197624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197624		ASN49K	Potatoes and fertilizers (LMIO19_bulves)	C++20	100 / 100	641 ms	55212 KiB

bulves

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
using i64 = long long;
#define int long long
std::mt19937 rng(69);
signed main()
{
    int n;
    std::cin>>n;
    std::vector<int>extra(n);
    int all_extra = 0;
    for(int i=0;i<n;i++)
    {
        int a,b;
        std::cin>>a>>b;
        extra[i]=a-b;

        all_extra+=extra[i];
    }
    std::multiset<int>a,b;
    a.insert(0);
    b.insert(0);
    int lazy_a=0,lazy_b=0;
    for(int i=1;i<n;i++)
    {
        //
        lazy_b+=extra[i];
        if(extra[i]<0)
        {
            lazy_a+=extra[i];
        }
        //adaug pante

        a.insert(-lazy_a);
        b.insert(-lazy_b);
        while(*a.rbegin()+lazy_a>*b.begin()+lazy_b)
        {
            int aa=*a.rbegin();
            int bb=*b.begin();
            a.erase(a.find(aa));
            b.erase(b.find(bb));
            aa+=lazy_a-lazy_b;
            bb+=-lazy_a+lazy_b;
            a.insert(bb);
            b.insert(aa);
        }
    }
    int last=0,panta=-n;
    i64 rez=0;
    for(auto &oldc:a)
    {
        int c=oldc+lazy_a;
        c=std::min(c,all_extra);
        if(c>last)
        {
            rez-=panta*(c-last);
            last=c;
        }
        panta++;
    }
    for(auto &oldc:b)
    {
        int c=oldc+lazy_b;
        c=std::min(c,all_extra);
        if(c>last)
        {
            rez-=panta*(c-last);
            last=c;
        }
        panta++;
    }
    rez-=panta*(all_extra-last);
    //std::cout<<rez<<' ';

    //calculez pl mea dp ul in all_extra
    std::vector<int>need(n+1,0);
    for(int i=0;i<n;i++)
    {
        if(extra[i]<0)
        {
            need[i]=-extra[i];
        }
    }
    need[n]=all_extra+1;
    for(int i=0,j=0;i<n;i++)
    {
        int xd=extra[i];
        while(xd>0)
        {
            int mn=std::min(xd , need[j]);
            need[j]-=mn;
            xd-=mn;
            rez+=abs(i-j)*mn;
            while(need[j]==0)
            {
                j++;
            }
        }
    }
    std::cout<<rez;
}
/*
2
2 0
0 1
 */

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36