제출 #423034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423034		rumen_m	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	308 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 100005;
long long ans[maxn][2];
long long n,m,k;
vector <pair <long long,long long> > w,p;
bool cmp(pair <long long,long long> i, pair <long long,long long> j)
{
    if(i.first==j.first)return i.second>j.second;
    return i.first<j.first;
}
struct CVH
{
   vector < pair <long long,long long> > lines;
   long long px;
   CVH()
   {
       lines.clear();
       lines.push_back({0,0});
       px = 0;
   }
   double intersect( pair <long long, long long> l1, pair <long long,long long> l2)
   {
       return (double)(l2.second-l1.second)/(l1.first-l1.first);
   }
   void add_line(long long a, long long b)
   {
       while(lines.size()>=2)
       {
           auto l1 = lines.back();
           auto l2 = lines[lines.size()-2];
           if(intersect(l1,l2)>intersect(l2,{a,b}))lines.pop_back();
           else
            break;
       }
       lines.push_back({a,b});
   }
   pair <long long,long long> query(long long x)
   {
       while(px<lines.size()-1)
       {
           if(lines[px].first*x+lines[px].second>=lines[px+1].first*x+lines[px+1].second)px++;
       }
       return lines[px];
   }

};
long long ANS[maxn];
long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c) {
    n = _n;
    m = _m;
    k = _k;
    w.resize(n);
    long long i;
    for(i=0;i<_r.size();i++)
    {
        w[i].first = min(_r[i],_c[i]);
        w[i].second = max(_r[i],_c[i]);
    }
    sort(w.begin(),w.end(),cmp);
    p.push_back({0,0});
    for(i=0;i<n;i++)
    {
        if(p.back().first<=w[i].first&&w[i].second<=p.back().second)continue;
        p.push_back(w[i]);
    }
    CVH u,v;


    for(long long j = 1; j<=k; j++)
    {
        u = CVH();
        for(long long i=1;i<p.size();i++)
        {
            //cout <<j <<" :: "<<i<<" :::: "<<p[i].first<<" "<<p[i].second<<endl;
            auto  d = u.query(p[i].second);
           long long  ans = d.first*p[i].second+d.second+p[i].second*p[i].second;
           long long M = -2*(p[i].first-1);
           long long B = ANS[i] + (p[i].first-1)*(p[i].first-1) - max((long long) 0,p[i-1].second-p[i].first+1)* max((long long)0,p[i-1].second-p[i].first+1);
           //cout<<M<<" "<<B<<endl;
           u.add_line(M,B);
           ANS[i] = ans;
           //cout<<"&& "<<i<<" "<<ANS[i]<<endl;
        }
    }
   // cout<<ANS[p.size()-1]<<endl;
    return ANS[p.size()-1];
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In member function 'double CVH::intersect(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
aliens.cpp:25:44: warning: division by zero [-Wdiv-by-zero]
   25 |        return (double)(l2.second-l1.second)/(l1.first-l1.first);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
aliens.cpp: In member function 'std::pair<long long int, long long int> CVH::query(long long int)':
aliens.cpp:41:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |        while(px<lines.size()-1)
      |              ~~^~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:56:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(i=0;i<_r.size();i++)
      |             ~^~~~~~~~~~
aliens.cpp:74:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(long long i=1;i<p.size();i++)
      |                           ~^~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40