oj.uz

Submission #340431

# Submission time Handle Problem Language Result Execution time Memory
340431 2020-12-27T15:27:55 Z Ahmad_Hasan Cover (COCI18_cover) C++17
120 / 120
 82 ms 876 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<long long >dp;
long long slv(int cr=0){
    if(cr>=n)
        return 0ll;
    if(dp[cr]!=-1ll)
        return dp[cr];
    long long ret=1e16;
    int nwcr=cr+1;
    ret=vps[cr].first*vps[cr].second+slv(nwcr);
    long long x=vps[cr].first,y=vps[cr].second;
    while(nwcr<n){
        x=max(x,vps[nwcr].first);
        y=max(y,vps[nwcr].second);
        ret=min(ret,x*y+slv(nwcr+1));
        nwcr++;
    }
    return dp[cr]=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<long long>(5005,-1ll);

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

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

*/

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 29 ms 620 KB Output is correct
10 Correct 82 ms 876 KB Output is correct