Submission #144771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144771	2019-08-17T16:27:18 Z	mariadinca	Cover (COCI18_cover)	C++14	120 / 120	11 ms	760 KB

cover

#include <iostream>
#define x first
#define y second
#include <algorithm>

using namespace std;

long long n, m, i, j, k, ymin, ymax, verticala, verticalaanterioara, sol[20002], sum;
pair<long long, long long> v[20002], d[20002];

int main(){
    cin>>n;
    m = n;
    for(i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        v[++m].x =  v[i].x, v[m].y = -v[i].y;
        v[++m].x = -v[i].x, v[m].y = -v[i].y;
        v[++m].x = -v[i].x, v[m].y =  v[i].y;
    }
    sort(v+1, v+m+1);
    for(i=1;i<=m;i++){
        if(v[i].x > 0)
            break;
        ymax = 0;
        ymin = v[i].y;
        for(j=i;v[j].x == v[i].x;j++)
            if(v[j].y > 0)
                ymax = v[j].y;
        verticala = max(ymax, -ymin);
        /// deci dreptunghiul curent are aria egala cu -4*verticala*v[i].x
        if(verticala > verticalaanterioara){
            verticalaanterioara = verticala;
            d[++k].x = -2*v[i].x;
            d[k].y = 2*verticala;
        }
        i = j;
    }
    for(i=1;i<=k;i++){
        sol[i] = d[1].x*d[i].y;
        for(j=1;j<=i;j++){
            sol[i] = min(sol[i], sol[j-1] + d[j].x*d[i].y);
        }
    }
    cout<<sol[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	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 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	376 KB	Output is correct
8	Correct	4 ms	504 KB	Output is correct
9	Correct	8 ms	632 KB	Output is correct
10	Correct	11 ms	760 KB	Output is correct