oj.uz

Submission #144045

# Submission time Handle Problem Language Result Execution time Memory
144045 2019-08-15T19:31:49 Z AldeaDanut Cover (COCI18_cover) C++14
120 / 120
 16 ms 2040 KB 
#include <iostream>
#include <set>

using namespace std;

struct dr{
    long long dimx;
    long long dimy;
} d[20001];

struct pct{
    long long x;
    long long y;
} v[20001];

long long n,i,j,x,y,k,m,M,D[20001];
set <pair<long long,long long> > s;

int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x>>y;
        s.insert(make_pair( x, y));
        s.insert(make_pair( x,-y));
        s.insert(make_pair(-x, y));
        s.insert(make_pair(-x,-y));
    }
    n=0;

    for(set<pair<long long,long long> >::iterator it=s.begin();it!=s.end();it++){
        v[++n].x=it->first;
        v[n].y=it->second;
    }

    m=v[1].y;
    M=v[1].y;
    for(i=2;i<=n;i++){
        if(v[i].x>=0)
            break;

        if(v[i].x==v[i-1].x){
            m=min(m,v[i].y);
            M=max(M,v[i].y);
        }else{
            if(k==0 || M-m>d[k].dimy ){
                d[++k].dimx=-2*v[i-1].x;
                d[k].dimy=M-m;
            }
            m=v[i].y;
            M=v[i].y;
        }
    }

    if(k==0 || M-m>d[k].dimy){
        d[++k].dimx=-2*v[i-1].x;
        d[k].dimy=M-m;
    }

    for(i=1;i<=k;i++){
        D[i]=d[1].dimx*d[i].dimy;
        for(j=1;j<=i;j++)
            D[i]=min(D[i],D[j-1]+d[j].dimx*d[i].dimy);
    }
    cout<<D[k];

    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 11 ms 1400 KB Output is correct
10 Correct 16 ms 2040 KB Output is correct