Submission #1033944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033944		tuan121212	Art Exhibition (JOI18_art)	C++14	0 / 100	1 ms	2396 KiB

art

#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;
	}
}

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