제출 #1164802

#제출 시각아이디문제언어결과실행 시간메모리
1164802hynmjPotatoes and fertilizers (LMIO19_bulves)C++20
0 / 100
1 ms580 KiB
//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define vv vector<vi>
#define vp vector<pi>
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
const int INF = 1e18, MOD = 1e9+7, N = 2e5+7;
void solve()
{
    int n, k, e, m, ans = 0;
    cin >> n;
    vi a(n);
    vi b(n);
    map<int,int> fro;
    map<int,int> bac;
    rep(n)
    {
    	cin >> a[i] >> b[i];
        if (a[i])
        {
            fro[i]+=a[i];
        }
    }
    bac[-INF] = INF;
    fro[INF] = INF;
    int now;
    int temp, temp2;
    rep(n)
    {
        now = b[i];
        temp = fro.begin() -> ff;
        temp2 = bac.rbegin()  -> ff;
        while (now)
        {
            auto k = fro.begin();
            auto l = bac.rbegin();
            if (k->ff -i <= i - l->ff )
            {
                // ans+=k->ff - i;
                // cout << k->ff << " " << k->ss << endl;
                // cout << i-k->ff << endl;
                if (k->ss <= now)
                {
                    now-=k->ss;
                    ans += (k->ff - i)*k->ss;
                    // cout << k->ff << " " << k->ss << endl;
                    // cout << i-k->ff << endl;
                    fro.erase(k->ff);
                }
                else
                {
                    fro[k->ff]-=now;
                    ans+=  (k->ff - i)*now ;
                    // cout << k->ff << " " << k->ss << endl;
                    // cout << i-k->ff << endl;
                    now = 0;
                }
            }
            else
            {
                if (l->ss <= now)
                {
                    ans += (i - l->ff)*l->ss;
                    now-=l->ss;
                    // cout << l->ff << " " << l->ss << endl;
                    // cout << i-l->ff << endl;
                    bac.erase(l->ff);
                }
                else
                {
                    bac[l->ff]-=now;
                    ans+=  (i - l->ff)*now ;
                    // cout << l->ff << " " << l->ss << endl;
                    // cout << i-l->ff << endl;
                    now = 0;
                }
            }
            // cout << i << " "<< ans  <<" " << temp << " " <<temp2 << endl;
        }
        if (fro.find(i)!= fro.end())
        {
            bac[i]+=fro[i];
            fro.erase(i);
        }

        
        
        // bac[i] = fro[i];
    }
    
    






     cout << ans;
    // cout << a.size();
    // for (auto i: a){cout << i << " ";}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    rep(ans){
        // cout << "Case #" << i+1 << ": ";
        solve();ln;}}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...