이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
void solve() {
int n;
cin >> n;
vector<pll> a(n);
ll ans1 = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i].first >> a[i].second;
ans1 = max(ans1, a[i].second);
}
sort(all(a));
ll ans = a[0].second;
int opt = 0;
ll now = a[0].first + a[0].second;
for (int i = 1; i < n; ++i) {
now += a[i].second;
now -= a[i].first;
if (now > ans) {
ans = now;
opt = i;
}
now += a[i].first;
}
if (opt != 0) {
now = ans;
for (int j = 1; j < opt; ++j) {
now -= (a[j - 1].first + a[j - 1].second);
now += a[j].first;
ans = max(ans, now);
}
}
cout << max(ans, ans1) << en;
}
void stupid() {
int n;
cin >> n;
vector<pll> a(n);
ll ans = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i].first >> a[i].second;
ans = max(ans, a[i].second);
}
sort(all(a));
for (int i = 0; i < n; ++i) {
ll now = a[i].first + a[i].second;
for (int j = i + 1; j < n; ++j) {
now += a[j].second;
now -= a[j].first;
ans = max(ans, now);
now += a[j].first;
}
}
cout << ans << en;
}
int main() {
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
solve();
// stupid();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |