Submission #419416

#TimeUsernameProblemLanguageResultExecution timeMemory
419416TricksterArt Exhibition (JOI18_art)C++14
0 / 100
1 ms204 KiB
//Suleyman Atayew #include <algorithm> #include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <bitset> #include <queue> #include <cmath> #include <map> #include <set> #define N 500010 #define ff first #define ss second #define pb push_back #define ll long long #define mod 1000000007 #define pii pair <ll, ll> #define sz(a) (ll)(a.size()) ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; } using namespace std; ll n; pii p[N]; ll f(ll x) { ll ret = 0, sum = 0; for(ll i = 1; i <= n; i++) { sum += p[i].ss; if(i >= x) { ret = max(ret, sum - (p[i].ff - p[i-x+1].ff)); sum -= p[i-x+1].ss; } } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; ll ans = 0; for(ll i = 1; i <= n; i++) cin >> p[i].ff >> p[i].ss, ans = max(ans, p[i].ss); sort(p+1, p+n+1); ll l = 1, r = n; for(ll i = 20; i >= 0; i--) { ll md1 = l + (r-l)/3; ll md2 = r - (r-l)/3; if(f(md1) > f(md2)) r = md2-1; else if(f(md1) == f(md2)) l = md1, r = md2; else l = md1+1; } cout << max(f(l), ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...