oj.uz

답안 #145157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145157 2019-08-18T22:58:38 Z mihaican Cover (COCI18_cover) C++14
120 / 120
 17 ms 2024 KB 
#include <iostream>
#include <set>
#define dd 20010
using namespace std;
struct puncte {
    long long x;
    long long y;
}v[dd];
struct dr{
    long long dx;
    long long dy;
}v2[dd];
set<pair<long long,long long>>sset;
long long n,n2,x,y,k, minim, maxim, sol,d[dd],uituc;
int main(){
/*
6
1 20
3 17
5 15
8 12
9 11
10 10
*/
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>x>>y;
        sset.insert(make_pair(x,y));
        sset.insert(make_pair(-x,y));
        sset.insert(make_pair(x,-y));
        sset.insert(make_pair(-x,-y));
    }
    for(set<pair<long long, long long> >::iterator it = sset.begin();it!=sset.end();it++)
        v[++n2].x=it->first,v[n2].y =it->second;
    minim=v[1].y;
    maxim=v[1].y;
    for(long long i=2;i<=n2;i++){
        uituc=i;
        if(v[i].x>=0)
            break;
        if(v[i].x==v[i-1].x){
            maxim=max(maxim,v[i].y);
            minim=min(minim,v[i].y);
        }
        else{
            if(maxim-minim>v2[k].dy||k==0){
                v2[++k].dx=-v[i-1].x*2;
                v2[k].dy=maxim-minim;
            }
            maxim=v[i].y;
            minim=v[i].y;
        }
    }
    if(k==0||maxim-minim>v2[k].dy){
        v2[++k].dx=-v[uituc-1].x*2;
        v2[k].dy=maxim-minim;
    }




    //d[i]=suma min pt primele i triunghiuri



    for(long long i=1;i<=k;i++){
        d[i]=v2[1].dx*v2[i].dy;
        for(long long j=i;j>=1;j--){
            d[i]=min(d[j-1]+v2[j].dx*v2[i].dy,d[i]);
        }
    }
    cout<<d[k];
}

Subtask #1
120.0 / 120.0

# 결과 실행 시간 메모리 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 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 10 ms 1272 KB Output is correct
10 Correct 17 ms 2024 KB Output is correct