#include <bits/stdc++.h>
using namespace std;
bool comp(pair<int,int>a,pair<int,int>b){
if(a.first==b.first)
return a.second>b.second;
return a.first>b.first;
}
vector<pair<long long,long long> >vps;
int n;
vector<vector<long long> >dp;
long long slv(int cr=0,int lst=0){
if(cr==n-1){
long long ret=max(vps[cr].first,vps[lst].first)* max(vps[cr].second,vps[lst].second);
return ret;
}
if(dp[cr][lst]!=-1ll)
return dp[cr][lst];
long long ret=1e17;
int nwcr=cr+1;
while(nwcr<n&&vps[nwcr].second<=vps[cr].second) nwcr++;
if(nwcr<n)
ret=min(ret,slv(nwcr,lst));
ret=min(ret,max(vps[cr].first,vps[lst].first)* max(vps[cr].second,vps[lst].second)+((nwcr<n)?slv(nwcr,nwcr):0ll));
return dp[cr][lst]=ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
vps=vector<pair<long long,long long> >(n);
for(int i=0;i<n;i++){
cin>>vps[i].first>>vps[i].second;
vps[i].first=abs(vps[i].first);
vps[i].second=abs(vps[i].second);
}
sort(vps.begin(),vps.end(),comp);
dp=vector<vector<long long> >(500,vector<long long>(500,-1ll));
cout<<4*slv()<<'\n';
return 0;
}/**
3
19 7
30 9
10 25
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2312 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2284 KB |
Output is correct |
| 8 |
Runtime error |
5 ms |
4588 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
6 ms |
4588 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
7 ms |
4716 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
