oj.uz

Submission #145049

# Submission time Handle Problem Language Result Execution time Memory
145049 2019-08-18T14:04:05 Z Mihnea Cover (COCI18_cover) C++14
120 / 120
 16 ms 1912 KB 
#include<iostream>
#include<set>
using namespace std;
long long n,x,y,k;
long long D[20001];
set<pair <long long,long long> >s;
set< pair<long long,long long> >::iterator it;
struct elem{
    long long x;
    long long y;
};

struct drept{
    long long dimx;
    long long dimy;
};

drept d[20001];
elem e[20001];

int main(){
    cin>>n;
    for(int 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(it=s.begin();it!=s.end();it++){
        e[++n].x=it->first;
        e[n].y=it->second;
    }
    long long minim=e[1].y;
    long long maxim=e[1].y;
    int i=2;
    for(;i<=n;i++){
        if(e[i].x>=0)
            break;
        if(e[i].x==e[i-1].x){
            minim=min(minim,e[i].y);
            maxim=max(maxim,e[i].y);
        }
        else{
            if(k==0 || maxim-minim>d[k].dimy){
                d[++k].dimx=-2 * e[i-1].x;
                d[k].dimy=maxim-minim;
            }
            minim=e[i].y;
            maxim=e[i].y;
        }
    }
    if(k==0 || maxim-minim>d[k].dimy){
        d[++k].dimx= -2 * e[i-1].x;
        d[k].dimy=maxim-minim;
    }

    for(i=1;i<=k;i++){
        D[i]=d[1].dimx * d[i].dimy;
        for(int 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 256 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 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 10 ms 1272 KB Output is correct
10 Correct 16 ms 1912 KB Output is correct