Submission #294502

#	Time	Username	Problem	Language	Result	Execution time	Memory
294502		daniel920712	Aliens (IOI16_aliens)	C++14	41 / 100	2080 ms	75768 KiB

aliens

/*#include "aliens.h"
#include <algorithm>
#include <deque>
using namespace std;
struct A
{
    long long a;
    long long b;
}Node[100005],ttt[100005];
bool ok[4005]={0};
long long DP[4005][4005]={0};
bool have[4005][4005];
long long tt[4005];
vector < pair < long long , long long > > L;
bool cmp(A a,A b)
{
    return a.a<b.a||a.a==b.a&&a.b<b.b;
}
long long F(int N,int M)
{
    long long i,t;
    if(N==-1) return 0;
    if(M==0) return 1e18;
    if(have[N][M]) return DP[N][M];
    DP[N][M]=1e18;
    have[N][M]=1;
    t=Node[N].b;
    for(i=N;i>=0;i--) DP[N][M]=min(DP[N][M],F(i-1,M-1)+Node[i].b*Node[i].b-2*Node[i].b*(Node[N].a+1));

    DP[N][M]+=(Node[N].a+1)*(Node[N].a+1);
    DP[N][M]-=max((long long) 0,Node[N].a-Node[N+1].b+1)*max((long long) 0,Node[N].a-Node[N+1].b+1);
    return DP[N][M];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    int i,j,N=0;
    for(i=0;i<n;i++)
    {
        ttt[i].a=(long long) max(r[i],c[i]);
        ttt[i].b=(long long) min(r[i],c[i]);
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==j||ttt[i].a==ttt[j].a&&ttt[i].b==ttt[j].b) continue;
            if(ttt[i].a>=ttt[j].a&&ttt[i].b<=ttt[j].b) ok[j]=1;
        }
    }
    for(i=0;i<n;i++) if(!ok[i]) Node[N++]=ttt[i];
    sort(Node,Node+N,cmp);
    Node[N].b=1e9;
    tt[N]=1e9;
    for(i=N-1;i>=0;i--) tt[i]=min(tt[i+1],Node[i].b);
    for(j=0;j<N;j++) DP[j][0]=1e18;
    for(i=1;i<=k;i++)
    {
        L.clear();
        for(j=0;j<N;j++)
        {
            DP[j][i]=1e18;
            if(j==0) L.push_back(make_pair(-2*Node[j].b,(Node[j].b)*Node[j].b));
            else L.push_back(make_pair(-2*Node[j].b,DP[j-1][i-1]+(Node[j].b)*Node[j].b));
            for(auto k:L) DP[j][i]=min(DP[j][i],k.first*(Node[j].a+1)+k.second);
            for(auto k:L)
            {

                if(i==2&&j==58)
                {
                    printf("%lld %lld %lld\n",k.first,k.second,(Node[j].a+1));
                }
            }
            DP[j][i]+=(Node[j].a+1)*(Node[j].a+1);
            DP[j][i]-=max((long long) 0,Node[j].a-Node[j+1].b+1)*max((long long) 0,Node[j].a-Node[j+1].b+1);
            //printf("%d %d %lld\n",i,j,DP[j][i]);
        }

    }

    return DP[N-1][k];
}
*/
#include "aliens.h"
#include <algorithm>
#include <deque>
using namespace std;
struct A
{
    long long a;
    long long b;
}Node[100005],ttt[100005];
bool ok[4005]={0};
long long DP[4005][4005]={0};
bool have[4005][4005];
long long tt[4005];
deque <  pair < long long , long long >  > L;
bool cmp(A a,A b)
{
    return a.a<b.a||a.a==b.a&&a.b<b.b;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    int i,j,N=0;
    pair < long long , long long > x,y,z;
    for(i=0;i<n;i++)
    {
        ttt[i].a=(long long) max(r[i],c[i]);
        ttt[i].b=(long long) min(r[i],c[i]);
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==j||ttt[i].a==ttt[j].a&&ttt[i].b==ttt[j].b) continue;
            if(ttt[i].a>=ttt[j].a&&ttt[i].b<=ttt[j].b) ok[j]=1;
        }
    }
    for(i=0;i<n;i++) if(!ok[i]) Node[N++]=ttt[i];
    sort(Node,Node+N,cmp);
    Node[N].b=1e9;
    tt[N]=1e9;
    for(i=N-1;i>=0;i--) tt[i]=min(tt[i+1],Node[i].b);
    for(j=0;j<N;j++) DP[j][0]=1e18;
    for(i=1;i<=k;i++)
    {
        L.clear();
        for(j=0;j<N;j++)
        {
            DP[j][i]=1e18;

            if(j==0) z=make_pair(-2*Node[j].b,(Node[j].b)*Node[j].b);
            else z=make_pair(-2*Node[j].b,DP[j-1][i-1]+(Node[j].b)*Node[j].b);

            if(!L.empty())
            {
                x=L.back();
                L.pop_back();
                while(!L.empty()&&((double) (z.first-x.first)/(double) (x.second-z.second))>=((double) (L.back().first-x.first)/(double) (x.second-L.back().second)))
                {
                    x=L.back();
                    L.pop_back();
                }
                L.push_back(x);

            }

            if(L.empty()||L.back().first!=z.first) L.push_back(z);

            x=L.front();
            L.pop_front();
            while(!L.empty()&&x.first*(Node[j].a+1)+x.second>=L.front().first*(Node[j].a+1)+L.front().second)
            {
                x=L.front();
                L.pop_front();
            }
            L.push_front(x);
            DP[j][i]=x.first*(Node[j].a+1)+x.second;

            /*if(i==2&&j==58)
            {
                //printf("%lld %lld %lld\n",x.first,x.second,(Node[j].a+1));
                L.pop_front();
                printf("%lld %lld %lld\n",L.front().first,L.front().second,(Node[j].a+1));
                L.push_back(x);
            }*/


            DP[j][i]+=(Node[j].a+1)*(Node[j].a+1);
            DP[j][i]-=max((long long) 0,Node[j].a-Node[j+1].b+1)*max((long long) 0,Node[j].a-Node[j+1].b+1);

        }
    }

    return DP[N-1][k];
}

Compilation message (stderr)

aliens.cpp: In function 'bool cmp(A, A)':
aliens.cpp:99:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |     return a.a<b.a||a.a==b.a&&a.b<b.b;
      |                     ~~~~~~~~^~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:115:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  115 |             if(i==j||ttt[i].a==ttt[j].a&&ttt[i].b==ttt[j].b) continue;
      |                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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