Submission #272121

#	Time	Username	Problem	Language	Result	Execution time	Memory
272121		erray	Art Exhibition (JOI18_art)	C++17	100 / 100	262 ms	15380 KiB

art

// author: erray
#include<bits/stdc++.h>
 
using namespace std;

template<typename T, typename F> string to_string(pair<T, F> p);
string to_string(string s) {
  return '"' + s + '"';
}
string to_string(char c) {
  return (string) "'" + c + "'";
}
string to_string(const char* p) {
  return to_string((string) p);
}
string to_string(bool B) {
  return (B ? "true" : "false");
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < (int) v.size(); ++i) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template<size_t T> string to_string(bitset<T> bs) {
  return bs.to_string();
}
template<typename T> string to_string(T v) {
  string res = "{";
  for (auto& el : v) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(el);
  }
  res += "}";
  return res;
}
template<typename T, typename F> string to_string(pair<T, F> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" , debug_out(__VA_ARGS__)
#else
#define debug(...) (void) 37
#endif
 
int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<long long, int>> a(n);
  long long mx = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i].first >> a[i].second;
    mx = max((long long) a[i].second, mx);
  }
  sort(a.begin(), a.end());
  long long sum, bef;
  vector<int> l;
  for (int i = 0; i < n; ++i) {
    if (a[i].first - bef >= sum || i == 0) {
      bef = a[i].first;
      sum = 0;
      l.push_back(i);
    }
    sum += a[i].second;
  } 
  vector<int> r;
  for (int i = n - 1; i >= 0; --i) {
    if (bef - a[i].first >= sum || i == n - 1) {
      sum = 0;
      bef = a[i].first;
      r.push_back(i);
    } 
    sum += a[i].second;
  }
  reverse(r.begin(), r.end());
  debug(l, r);
  vector<long long> pref;
  
  for (auto el : a) {
    pref.push_back((pref.empty() ? 0 : pref.back()) + el.second);
  }
  for (int i = 0; i < n; ++i) {
    int tl = *--lower_bound(l.begin(), l.end(), i + 1), tr = *lower_bound(r.begin(), r.end(), i);
    debug(i, tl, tr);
    mx = max(pref[tr] - (tl ? pref[tl - 1] : 0) - (a[tr].first - a[tl].first), mx);
  }
  cout << mx << '\n';
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:80:13: warning: 'bef' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     if (bef - a[i].first >= sum || i == n - 1) {
      |         ~~~~^~~~~~~~~~~~
art.cpp:80:33: warning: 'sum' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     if (bef - a[i].first >= sum || i == n - 1) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50