oj.uz

Submission #649567

# Submission time Handle Problem Language Result Execution time Memory
649567 2022-10-10T15:42:53 Z dimonce Sails (IOI07_sails) C++17
55 / 100
 100 ms 13140 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 25 ms 11520 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3956 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 6620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 12764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 12932 KB Output is correct
2 Correct 63 ms 11976 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 13140 KB Output isn't correct
2 Halted 0 ms 0 KB -