oj.uz

답안 #553681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553681 2022-04-26T15:12:43 Z SmolBrain 학교 설립 (IZhO13_school) C++17
100 / 100
 111 ms 14264 KB 
// Om Namah Shivaya
// GM in 98 days

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
template<typename T> void amin(T &a, T b) { a = min(a, b); }
template<typename T> void amax(T &a, T b) { a = max(a, b); }

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    // code reference: https://oj.uz/submission/524090
    ll n, m, s; cin >> n >> m >> s;
    vector<pll> a(n + 5);
    rep1(i, n) cin >> a[i].ff >> a[i].ss;

    auto comp = [&](pll p1, pll p2) {
        return p1.ff - p1.ss > p2.ff - p2.ss;
    };

    sort(a.begin() + 1, a.begin() + n + 1, comp);

    vector<ll> music(n + 5), sports(n + 5);
    priority_queue< ll, vector<ll>, greater<ll> > pq;
    ll sum = 0;

    rep1(i, n) {
        pq.push(a[i].ff);
        sum += a[i].ff;

        while (sz(pq) > m) {
            sum -= pq.top();
            pq.pop();
        }

        music[i] = sum;
    }

    while (!pq.empty()) pq.pop();
    sum = 0;

    rev(i, n, 1) {
        pq.push(a[i].ss);
        sum += a[i].ss;

        while (sz(pq) > s) {
            sum -= pq.top();
            pq.pop();
        }

        sports[i] = sum;
    }

    ll ans = 0;

    rep(i, n + 1) {
        ll curr = music[i] + sports[i + 1];
        amax(ans, curr);
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

school.cpp: In function 'void solve(int)':
school.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   94 |         while (sz(pq) > m) {
      |                       ^
school.cpp:109:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  109 |         while (sz(pq) > s) {
      |                       ^
school.cpp: In function 'void usaco(std::string)':
school.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 15 ms 2252 KB Output is correct
14 Correct 27 ms 3968 KB Output is correct
15 Correct 48 ms 7152 KB Output is correct
16 Correct 58 ms 10092 KB Output is correct
17 Correct 87 ms 10784 KB Output is correct
18 Correct 100 ms 11724 KB Output is correct
19 Correct 99 ms 12556 KB Output is correct
20 Correct 111 ms 14264 KB Output is correct