Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
119162 陈家宝 土地购买 C++ 通过 100 15 MS 1048 KB 863 2024-01-04 13:34:21

Tests(10/10):


#include<bits/stdc++.h> using namespace std; const int N = 50010; struct node{ int x,y; bool operator < (const node &b) const{ return x == b.x ? y > b.y : x > b.x; } }a[N]; int n; long long que[N],dp[N]; double Slop(int i,int j) { return 1.0 * (dp[i] - dp[j]) / (a[j + 1].x - a[i + 1].x); } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin >> n; for (int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y; sort(a + 1,a + n + 1); int k = 0; for (int i = 1;i <= n;i++) if (a[i].y > a[k].y) a[++k] = a[i]; n = k; int l = 1,r = 0; que[++r] = 0; for (int i = 1;i <= n;i++){ while (l < r && Slop(que[l],que[l + 1]) <= a[i].y) ++l; dp[i] = dp[que[l]] + (long long)a[que[l] + 1].x * a[i].y; while (l < r && Slop(que[r - 1],que[r]) >= Slop(que[r],i)) --r; que[++r] = i; } cout << dp[n]; return 0; }


测评信息: