Submission #1269378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269378		picrad	Art Exhibition (JOI18_art)	C++20	100 / 100	125 ms	12108 KiB

art

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<ll,ll> pii;
 
const int maxn = 5e5+5,MOD = 1e9+7;
ll N,dp[maxn],ans;
pii A[maxn];
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  for(int i =1; i <= N; i++) cin >> A[i].fi >> A[i].se;
  sort(A+1,A+N+1);
  for(int i =1; i <= N; i++){
    dp[i] = max(0LL,dp[i-1] - (A[i].fi-A[i-1].fi))+A[i].se;
    ans = max(ans,dp[i]);
  }
  cout << ans << '\n';
}

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