oj.uz

Submission #1117213

# Submission time Handle Problem Language Result Execution time Memory
1117213 2024-11-23T02:02:27 Z vjudge1 Art Exhibition (JOI18_art) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define LL long long
 
#define rep(i, x) for(auto &i : (x))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define left(x) ((x)<<1)
#define right(x) ((x)>>1)
#define LSOne(x) (x & -(x))
 
using namespace std;
using T = pair<pair<int, int>, int>;
 
const int SZ = 2e5 + 1;
const LL MOD = 1e9 + 7; 
const LL INF = 1e18 + 1;
 
LL bp (LL b, LL e, LL m = MOD) {
 if ( e == 0 ) return 1;
 LL T = bp(b, e / 2);
 T *= T; T %= m;
 if ( e & 1 ) T *= b;
 return T %= m;
}
 
LL nv_i (LL a) { return bp(a, MOD - 2); };
LL gcd (LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); }
LL lcm(LL a, LL b) { return (a * (b / gcd(a, b))); }
LL ceil (LL a, LL b) { return ((a + b - 1) / b); }
 
void solve() {
  int n;
  cin >> n;

  vector<pair<LL, LL>> ARTW(n + 1);
  vector<LL> AUX(n + 1);
  for(int i = 1; i <= n; i ++) {
    cin >> ARTW[i].F >> ARTW[i].S;
  }
  
  sort(all(ARTW));

  for(int i = 1; i <= n; i ++) {
    ARTW[i].S += ARTW[i - 1].S;
    AUX[i] = ARTW[i].S;
  }

  pair<LL, int> mx = {0, 0};
  for(int i = 1; i <= n; i ++) {
    ARTW[i].S -= ARTW[i].F;
    if(ARTW[i].S >= mx.F) {
      mx.F = ARTW[i].S;
      mx.S = i;
    }
  }
  
  LL ans = 0;

  for(int i = 1; i <= mx.S; i ++) {
    LL sum = ARTW[mx.S].S - AUX[i - 1] + ARTW[i].F;
    ans = max(ans, sum);
  }
  
  for(int i = mx.S + 1; i <= n; i ++) {
    LL sum = ARTW[i].S - AUX[i - 1] + ARTW[i].F;
    ans = max(ans, sum);
  }
  cout << ans;
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
 
  solve();
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -