呵呵
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 1000010 4 #define LL long long 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 7 int n, t, a[N], s[N]; 8 LL ans, b[N], sum[N]; 9 10 inline LL read() 11 { 12 LL x = 0, f = 1; 13 char ch = getchar(); 14 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 15 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 16 return x * f; 17 } 18 19 int main() 20 { 21 int i; 22 n = read(); 23 for(i = 1; i <= n; i++) a[i] = read(), b[i] = read(); 24 a[0] = a[n + 1] = 1e9; 25 for(i = 1; i <= n + 1; i++) 26 { 27 while(t && a[s[t]] < a[i]) sum[i] += b[s[t--]]; 28 s[++t] = i; 29 } 30 t = 0; 31 for(i = n; i >= 0; i--) 32 { 33 while(t && a[s[t]] < a[i]) sum[i] += b[s[t--]]; 34 s[++t] = i; 35 } 36 for(i = 1; i <= n; i++) ans = max(ans, sum[i]); 37 printf("%lld ", ans); 38 }