Submission #939106

#	Time	Username	Problem	Language	Result	Execution time	Memory
939106		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	141 ms	45412 KiB

art

#include <bits/stdc++.h>  
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast") 
//#pragma comment(linker, "/stack:200000000") 
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" ) 
#pragma GCC optimize("unroll-loops")
/* 
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer") 
#pragma GCC optimize("vpt") 
#pragma GCC optimize("rename-registers") 
#pragma GCC optimize("move-loop-invariants") 
#pragma GCC optimize("unswitch-loops") 
#pragma GCC optimize("function-sections") 
#pragma GCC optimize("data-sections") 
#pragma GCC optimize("branch-target-load-optimize") 
#pragma GCC optimize("branch-target-load-optimize2") 
#pragma GCC optimize("btr-bb-exclusive") 
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse") 
#pragma GCC optimize("-fgcse-lm") 
#pragma GCC optimize("-fipa-sra") 
#pragma GCC optimize("-ftree-pre") 
#pragma GCC optimize("-ftree-vrp") 
#pragma GCC optimize("-fpeephole2") 
#pragma GCC optimize("-ffast-math") 
#pragma GCC optimize("-fsched-spec") 
#pragma GCC optimize("-falign-jumps") 
#pragma GCC optimize("-falign-loops") 
#pragma GCC optimize("-falign-labels") 
#pragma GCC optimize("-fdevirtualize") 
#pragma GCC optimize("-fcaller-saves") 
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps") 
#pragma GCC optimize("-freorder-blocks") 
#pragma GCC optimize("-fschedule-insns") 
#pragma GCC optimize("inline-functions") 
#pragma GCC optimize("-ftree-tail-merge") 
#pragma GCC optimize("-fschedule-insns2") 
#pragma GCC optimize("-fstrict-aliasing") 
#pragma GCC optimize("-falign-functions") 
#pragma GCC optimize("-fcse-follow-jumps") 
#pragma GCC optimize("-fsched-interblock") 
#pragma GCC optimize("-fpartial-inlining") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("-freorder-functions") 
#pragma GCC optimize("-findirect-inlining") 
#pragma GCC optimize("-fhoist-adjacent-loads") 
#pragma GCC optimize("-frerun-cse-after-loop") 
#pragma GCC optimize("inline-small-functions") 
#pragma GCC optimize("-finline-small-functions") 
#pragma GCC optimize("-ftree-switch-conversion") 
#pragma GCC optimize("-foptimize-sibling-calls") 
#pragma GCC optimize("-fexpensive-optimizations") 
#pragma GCC optimize("inline-functions-called-once") 
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long 
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define dauzhan gay
#define popcount __builtin_popcount
#define int long long
const long double Eps = 1e-12; 
const int max1 = 1e9 + 100; 
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 2e5 + 100;
const int B = 1e6 + 1;
const ll INF = 1e18 + 100;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
    if(y < 0) return 0;
    if(y == 0) return 1;        
    if(y == 1) return x;
    if(y % 2 == 0) {
        ll now = binpow(x,y/2,md);
        return (1ll*now*now) % md;
    }
    else {
        ll now = binpow(x,y/2,md);
        return (1ll*((1ll*now*now) % md)*x) % md;
    }
}
/*
for(int i = 1;i <= n;i++) sp[0][i] = a[i];
for(int i = 1;i <= log2(n);i++) {
    for(int l = 1;l <= n;l++) {
        int r = l + (1 << i) - 1;
        if(r > n) break;
        int middle = l + (1 << (i - 1));
        sp[i][l] = max(sp[i - 1][l],sp[i - 1][middle]);
    }
}
int get(int l,int r) {
    int g = log2(r - l + 1);
    return max(sp[g][l],sp[g][r - (1 << g) + 1]);
} 
*/
vector <int> reb[B];
bool was[B];
int mx[B],mn[B];
void dfs1(int v) {
    mx[v] = v,mn[v] = v;
    was[v] = true;
    for(auto u:reb[v]) {
        if(was[u]) continue;
        dfs1(u);
        mx[v] = max(mx[v],mx[u]);
        mn[v] = min(mn[v],mn[u]);
    }
}
bool was2[B];
void dfs2(int v) {
    was2[v] = true;
    for(auto u:reb[v]) {

    }
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);    
    int n;
    cin >> n;
    pair <int,int> p[n + 1];
    for(int i = 1;i <= n;i++) cin >> p[i].f >> p[i].s;
    sort(p + 1,p + n + 1);
    for(int i = 2;i <= n;i++) {
    }
    int mx = p[n].s;
    int ans = p[n].s;
    for(int i = n - 1;i >= 1;i--) {
        mx-=p[i + 1].f - p[i].f;
        mx = max(mx,0ll);
        mx+=p[i].s;
        ans = max(ans,mx);
    }
    cout << ans << endl;
}
    
    
     
    
    

Compilation message (stderr)

art.cpp: In function 'void dfs2(long long int)':
art.cpp:125:14: warning: unused variable 'u' [-Wunused-variable]
  125 |     for(auto u:reb[v]) {
      |              ^

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