#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define el cout << '\n';
using namespace std;
const int N = 5e5+5;
const int inf = 1e18;
const int LG = 31;
const int MOD = 1e9+7;
//const int mod = 998244353;
int n;
pair<int,int> a[N];
int dp[N],pre[N];
pair<int,int> b[N];
bool cmp(pair<int,int> x, pair<int,int> y){
if(x.fi != y.fi) return x.fi < y.fi;
return x.se > y.se;
}
void solve(){
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i].fi >> a[i].se;
sort(a+1,a+1+n,cmp);
// for(int i=1; i<=n; i++){
// cout << a[i].fi << ' ' << a[i].se << '\n';
// }
// int mini = a[1].fi,val=a[1].se;dp[1] = a[1].se;
// int last = a[1].fi;
// for(int i=2; i<=n; i++){
// int x = dp[i-1] + a[i].se - (a[i].fi-last);
// if(x>dp[i-1]){
// last = a[i].fi;
// dp[i]=x;
// }
// else dp[i]=dp[i-1];
// cout << dp[i] << ' ';
// }
int cnt=1;
b[1] = {a[1].fi,a[1].se};
for(int i=2; i<=n; i++){
if(a[i].fi == a[i-1].fi){
b[cnt].se+=a[i].se;
}
else{
cnt++;
b[cnt] = {a[i].fi,a[i].se};
}
}
for(int i=1; i<=cnt; i++){
// cout << b[i].fi << ' ' << b[i].se << '\n';
pre[i] = pre[i-1] + b[i].se;
}
int ans = b[1].se;
for(int i=cnt; i>=2; i--){
ans = max(ans , pre[i] + b[1].fi - b[i].fi);
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
el;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
