This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
#define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int N = 500100;
void solve() {
int n;
cin>>n;
vii a(n);
for(int i=0; i<n; i++){
cin>>a[i].f>>a[i].s;
}
sort(all(a));
for(int i=0; i<a.size()-1; i++){
if(a[i].f==a[i+1].f){
a[i+1].s+=a[i].s;
a.erase(a.begin()+i);
i--;
}
}
n=a.size();
// for(int i=0; i<n; i++){
// cout<<a[i].f<<" "<<a[i].s<<en;
// }
vi p(n+1, 0), pl(n+1, 0), pr(n+1, 0);
for(int i=0; i<n; i++){
p[i+1] = p[i] + a[i].s;
}
for(int i=1; i<=n; i++){
pl[i] = a[i-1].f - p[i-1];
}
for(int i=1; i<=n; i++){
pr[i] = p[i] - a[i-1].f;
}
// for(int i=0; i<n; i++){
// cout<<a[i].f<<" "<<a[i].s<<" "<<p[i+1]<<" "<<pl[i+1]<<" "<<pr[i+1]<<en;
// }
// build(pl, 1, 0, n);
int mx=0, mx2=0;
int ans=0;
for(int i=0; i<=n; i++){
mx = max(mx, pl[i]);
ans = max(ans, pr[i]+mx);
}
cout<<ans;
}
signed main() {
fast_io;
int tc = 1;
// scanf("%d", &tc);
while (tc--)
solve();
}
Compilation message (stderr)
art.cpp: In function 'void solve()':
art.cpp:28:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0; i<a.size()-1; i++){
| ~^~~~~~~~~~~
art.cpp:54:15: warning: unused variable 'mx2' [-Wunused-variable]
54 | int mx=0, mx2=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... |