Submission #1197604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197604		ASN49K	Potatoes and fertilizers (LMIO19_bulves)	C++20	20 / 100	1092 ms	736 KiB

bulves

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
using i64 = long long;

std::mt19937 rng(69);
int 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::vector<int>pq;
    pq.push_back(0);
    pq.push_back(0);
    std::sort(all(pq));
    for(int i=1;i<n;i++)
    {
        //
        if(extra[i]<0)
        {
            //shitam la stanga totul
            for(auto &c:pq)
            {
                c+=extra[i];
            }
        }
        if(extra[i]>0)
        {
            for(int j=i;j<(int)pq.size();j++)
            {
                pq[j]+=extra[i];
            }
        }
        //addaug pante
        pq.push_back(0);
        pq.push_back(0);
        std::sort(all(pq));
    }
    int last=0,panta=-n;
    i64 rez=0;
    for(auto &c:pq)
    {
        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;
            ///std::cout<<mn<<' '<<i<<' '<<j<<'\n';
            while(need[j]==0)
            {
                j++;
            }
        }
    }
    std::cout<<rez;
}
/*
2
2 0
0 1
 */

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