oj.uz

Submission #712377

# Submission time Handle Problem Language Result Execution time Memory
712377 2023-03-18T17:36:48 Z Sam_a17 Schools (IZhO13_school) C++17
100 / 100
 239 ms 11528 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif

#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)

#define pb push_back
#define popf pop_front
#define popb pop_back

void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << 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(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'

// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();

  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
int n, m, s;

bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
  return a.first - a.second <= b.first - b.second;
}

void solve_() {
  cin >> n >> m >> s;

  vector<pair<long long, long long>> arr;
  for(int i = 1; i <= n; i++) {
    int x, y; cin >> x >> y;
    arr.emplace_back(x, y);
  }

  sort(all(arr), cmp);
  vector<long long> pref(sz(arr) + 2), suf(sz(arr) + 3);

  priority_queue<long long> q;
  pref[0] = 0;
  long long sum = 0;
  for(int i = 0; i < n; i++) {
    sum += arr[i].second;
    q.push(-arr[i].second);
    if(sz(q) > s) {
      sum = sum + q.top();
      q.pop();
    }
    pref[i + 1] = sum;
  }

  while(!q.empty()) q.pop();

  suf[n + 1] = 0, sum = 0;
  for(int i = n - 1; i >= 0; i--) {
    sum += arr[i].first;
    q.push(-arr[i].first);
    if(sz(q) > m) {
      sum = sum + q.top();
      q.pop();
    }
    suf[i + 1] = sum;
  }

  long long answ = 0;
  for(int i = 0; i <= n; i++) {
    answ = max(answ, pref[i] + suf[i + 1]);
  }
  
  cout << answ << endl;
}

int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };

  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);

  return 0;
}

Compilation message

school.cpp: In function 'void setIO(std::string)':
school.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.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
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 596 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 468 KB Output is correct
13 Correct 12 ms 1872 KB Output is correct
14 Correct 36 ms 3148 KB Output is correct
15 Correct 58 ms 5372 KB Output is correct
16 Correct 86 ms 9276 KB Output is correct
17 Correct 152 ms 8928 KB Output is correct
18 Correct 172 ms 9624 KB Output is correct
19 Correct 197 ms 10268 KB Output is correct
20 Correct 239 ms 11528 KB Output is correct