Submission #145046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145046	2019-08-18T13:53:32 Z	Mihnea	Cover (COCI18_cover)	C++14	24 / 120	16 ms	1912 KB

cover

#include<iostream>
#include<set>
using namespace std;
long long v[20010];
long long n,k,x,y;
set< pair<long long,long long> > s;
struct elem{
    long long x;
    long long y;
};

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

elem e[20010];
drept d[20010];
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(set< pair<long long,long long> >::iterator 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) {
            maxim=max(maxim,e[i].y);
            minim=min(minim,e[i].y);
        }
        else{
            if(k==0||maxim-minim>d[k].dimy) {
                d[++k].dimx=-e[i-1].x*2;
                d[k].dimy=maxim-minim;
            }
            maxim=e[i].y;
            minim=e[i].y;
        }
    }
    if(k==0||maxim-minim>d[k].dimy){
        d[++k].dimx=-e[i].x*2;
        d[k].dimy=maxim-minim;
    }
    for(int i=1;i<=k;i++){
        v[i]=d[1].dimx*d[i].dimy;
        for(long long j=i;j>=1;j--){
            v[i]=min(v[i],v[j-1]+d[j].dimx*d[i].dimy);
        }
    }
    cout<<v[k];
    return 0;
}

Subtask #1

24.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	376 KB	Output isn't correct
3	Incorrect	2 ms	248 KB	Output isn't correct
4	Incorrect	2 ms	376 KB	Output isn't correct
5	Incorrect	2 ms	376 KB	Output isn't correct
6	Incorrect	2 ms	376 KB	Output isn't correct
7	Incorrect	3 ms	504 KB	Output isn't correct
8	Incorrect	4 ms	632 KB	Output isn't correct
9	Correct	11 ms	1272 KB	Output is correct
10	Correct	16 ms	1912 KB	Output is correct