oj.uz

Submission #649566

# Submission time Handle Problem Language Result Execution time Memory
649566 2022-10-10T15:39:16 Z dimonce Sails (IOI07_sails) C++14
55 / 100
 111 ms 13944 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n;
    cin>>n;
    int h[n], k[n], mx=0, sum=0;
    unordered_map<int, int> 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';
    int 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';
    int need=sum/mx,q, cur=0, still=mx;
    int res[mx+1]={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';
    int result=0;
    for (int i=1; i<=mx; ++i){
        result+=res[i]*(res[i]-1)/2;
    }
    cout<<result;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 21 ms 11608 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3724 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 27 ms 4328 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 13476 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 111 ms 13772 KB Output is correct
2 Correct 73 ms 12724 KB Output is correct

Subtask #11
0 / 10.0

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