oj.uz

Submission #712376

# Submission time Handle Problem Language Result Execution time Memory
712376 2023-03-18T17:35:09 Z Sam_a17 Schools (IZhO13_school) C++17
75 / 100
 228 ms 9404 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<int, int> a, pair<int, int> b) {
  return a.first - a.second <= b.first - b.second;
}

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

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

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

  priority_queue<int> q;
  pref[0] = 0;
  int 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;
  }

  int 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
75.0 / 100.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
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 464 KB Output is correct
13 Correct 13 ms 1480 KB Output is correct
14 Correct 30 ms 2520 KB Output is correct
15 Correct 54 ms 4616 KB Output is correct
16 Incorrect 83 ms 6740 KB Output isn't correct
17 Incorrect 166 ms 7248 KB Output isn't correct
18 Incorrect 170 ms 7760 KB Output isn't correct
19 Incorrect 189 ms 8348 KB Output isn't correct
20 Incorrect 228 ms 9404 KB Output isn't correct