oj.uz

답안 #97186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97186 2019-02-14T09:44:42 Z Kastanda 학교 설립 (IZhO13_school) C++11
70 / 100
 1892 ms 7012 KB 
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
template < int MXN >
struct SegTree
{
    int C[MXN * 4];
    ll S[MXN * 4];
    void Add(int i, int val, int id = 1, int l = 0, int r = MXN)
    {
        if (r - l < 2)
        {
            S[id] += 1LL * val * l;
            C[id] += val; return ;
        }
        if (i < md)
            Add(i, val, lc, l, md);
        else
            Add(i, val, rc, md, r);
        C[id] = C[lc] + C[rc];
        S[id] = S[lc] + S[rc];
    }
    ll _Get(int &k, int id = 1, int l = 0, int r = MXN)
    {
        if (!k) return 0LL;
        if (C[id] <= k)
            return k -= C[id], S[id];
        return (_Get(k, rc, md, r) + _Get(k, lc, l, md));
    }
    ll Get(int k)
    {
        int tmp = k;
        return (_Get(tmp));
    }
};
const int N = 300005, MXN = 100005;
int n, R, M;
pair < int , int > A[N];
int main()
{
    scanf("%d%d%d", &n, &R, &M);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &A[i].first, &A[i].second);
    sort(A, A + n); reverse(A, A + n);
    SegTree < MXN * 2 > P, S;
    for (int i = 0; i < n; i++)
        S.Add(A[i].second, 1);
    ll Mx = 0, sum = 0;
    for (int i = 0; i < R + M; i++)
    {
        sum += A[i].first;
        S.Add(A[i].second, -1);
        P.Add(A[i].second - A[i].first + MXN, 1);
        if (i >= R - 1)
            Mx = max(Mx, sum + P.Get(i + 1 - R) - (ll)(i + 1 - R) * MXN + S.Get(M - (i + 1 - R)));
    }
    return !printf("%lld\n", Mx);
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &R, &M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i].first, &A[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB Output isn't correct
5 Correct 5 ms 1792 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 10 ms 2944 KB Output is correct
8 Correct 10 ms 3584 KB Output is correct
9 Correct 10 ms 3592 KB Output is correct
10 Correct 11 ms 3456 KB Output is correct
11 Correct 10 ms 3456 KB Output is correct
12 Correct 11 ms 3456 KB Output is correct
13 Correct 36 ms 4188 KB Output is correct
14 Correct 58 ms 4444 KB Output is correct
15 Incorrect 112 ms 5624 KB Output isn't correct
16 Incorrect 204 ms 7012 KB Output isn't correct
17 Incorrect 1460 ms 5152 KB Output isn't correct
18 Incorrect 1703 ms 5496 KB Output isn't correct
19 Incorrect 1828 ms 5880 KB Output isn't correct
20 Correct 1892 ms 6616 KB Output is correct