oj.uz

Submission #340418

# Submission time Handle Problem Language Result Execution time Memory
340418 2020-12-27T15:05:27 Z Ahmad_Hasan Cover (COCI18_cover) C++17
0 / 120
 49 ms 65540 KB 
#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(5005,vector<long long>(5005,-1ll));
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()
{


    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);

    cout<<4*slv()<<'\n';

    return 0;
}/**
3
19 7
30 9
10 25

*/

Subtask #1
0 / 120.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 42 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 49 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 41 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 39 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 42 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 43 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 42 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 41 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 42 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)