oj.uz

답안 #144771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144771 2019-08-17T16:27:18 Z mariadinca Cover (COCI18_cover) C++14
120 / 120
 11 ms 760 KB 
#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

# 결과 실행 시간 메모리 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