Submission #649567

#	Time	Username	Problem	Language	Result	Execution time	Memory
649567		dimonce	Sails (IOI07_sails)	C++17	55 / 100	100 ms	13140 KiB

sails

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n;
    cin>>n;
    long long h[n], k[n], mx=0, sum=0;
    unordered_map<long long, long long> mph, mpk;
    for (int i=0; i<n; ++i){
        cin>>h[i]>>k[i];
        sum+=k[i];
        mx=max(h[i], mx);
        mpk[h[i]]+=k[i];
        ++mph[h[i]];
    }
    // cout<<mx<<'\n';
    long long hpr[mx+1], kpr[mx+1], curh=0, curk=0;
    for (int i=mx; i>0; --i){
        curh+=mph[i];
        curk+=mpk[i];
        hpr[i]=curh;
        kpr[i]=curk;
    }
    // for (int i=1; i<=mx; ++i){
    //     cout<<hpr[i]<<' ';
    // }
    // cout<<'\n';
    // for (int i=1; i<=mx; ++i){
    //     cout<<kpr[i]<<' ';
    // }
    // cout<<'\n';
    long long need=sum/mx,q, cur=0, still=mx;
    long long res[mx+1];
    for (int i=1; i<=mx; ++i){
        res[i]=0;
    }
    while (need>0){
        // cout<<need<<'\n';
        cur=0;
        for (int i=mx; i>0; --i){
            // hpr[i]-=cur;
            kpr[i]-=cur;
            q=min(need, min(hpr[i], kpr[i]));
            if (q==0){
                continue;
            }
            // cout<<need<<' '<<i<<' '<<q<<' '<<still<<'\n';
            // cout<<hpr[i]<<' '<<kpr[i]<<'\n';
            kpr[i]-=q;
            hpr[i]-=q;
            cur+=q;
            sum-=q;
            // cout<<hpr[i]<<' '<<kpr[i]<<'\n';
            if (hpr[i]==0 or kpr[i]==0){
                --still;
            }
            res[i]+=q;
        }
        if (kpr[1]==0){
            break;
        }
        if (still==0){
            // cout<<"WHAT?";
            break;
        }
        need=sum/still;
        // break;
    }
    // for (int i=1; i<=mx; ++i){
    //     cout<<res[i]<<' ';
    // }
    // cout<<'\n';
    if (sum>0){
        for (int i=1; i<=mx and sum>0; ++i){
            if (hpr[i]>0 and kpr[i]>0){
                ++res[i];
                --sum;
            }
        }
    }
    // for (int i=1; i<=mx; ++i){
    //     cout<<res[i]<<' ';
    // }
    // cout<<'\n';
    long long result=0;
    for (int i=1; i<=mx; ++i){
        result+=res[i]*(res[i]-1)/2;
    }
    cout<<result;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10