oj.uz

답안 #291829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291829 2020-09-05T20:31:18 Z Kastanda Sails (IOI07_sails) C++11
80 / 100
 44 ms 1528 KB 
// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n, H[N], K[N], C[N];
inline bool Solve(int md)
{
        memset(C, 0, sizeof(C));
        for (int i = 1; i <= n; i ++)
                C[H[i] - K[i] + 1] ++, C[H[i] + 1] --;
        for (int i = 1; i < N; i ++)
                C[i] += C[i - 1];
        ll LeftOver = 0;
        for (int i = N - 1; i; i --)
        {
                int tmp = min(LeftOver, (ll)md - C[i]);
                LeftOver -= tmp;
                C[i] += tmp;
                assert(C[i] <= md);
        }
        return !LeftOver;
}
int main()
{
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
                scanf("%d%d", &H[i], &K[i]);

        int le = 0, ri = N, md;
        while (ri - le > 1)
        {
                md = (le + ri) >> 1;
                if (Solve(md))
                        ri = md;
                else
                        le = md;
        }

        // How to do it with ri you ask? I don't know either ...
        Solve(ri);
        int ptr = 1;
        for (int i = N - 1; i; i --)
                if (C[i] == ri)
                {
                        while (ptr < i && C[ptr] == ri)
                                ptr ++;
                        if (ptr >= i)
                                break;
                        C[i] --;
                        C[ptr] ++;
                }
        for (int i = 1; i < N; i ++)
                assert(C[i] <= ri);
        bool Fail = 1;
        for (int i = 1; i < N; i ++)
                if (C[i] == ri)
                        Fail = 0;
        assert(!Fail);
        ll tot = 0;
        for (int i = 1; i < N; i ++)
                tot += (ll)C[i] * (C[i] - 1) / 2;
        printf("%lld\n", tot);
        return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
sails.cpp:28:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |                 scanf("%d%d", &H[i], &K[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 768 KB Output is correct
2 Correct 11 ms 896 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 768 KB Output is correct
2 Correct 19 ms 896 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 896 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 1152 KB Output isn't correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 1280 KB Output is correct
2 Correct 36 ms 1332 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 1408 KB Output is correct
2 Correct 34 ms 1408 KB Output is correct

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -