Submission #4486

#	Time	Username	Problem	Language	Result	Execution time	Memory
4486		ansol4328	막대기 (KOI13_game)	C++98	0 / 100	1000 ms	4216 KiB

game

#include<stdio.h>
#include<math.h>
#include<algorithm>

struct A
{
    int t, d;
};

A m[100002];

struct SORTF
{
    bool inline operator () (A a, A b)
    {
        return a.t < b.t;
    }
};

struct sortf
{
    bool inline operator () (A a, A b)
    {
        return a.d < b.d;
    }
};

int n, l;
long long td[100002], dd[100002];
long long dist[100002], max;

int input()
{
    int i, st, ed;
    scanf("%d %d",&n,&l);
    for(i=1 ; i<=n ; i++)
    {
        scanf("%d %d",&m[i].t,&m[i].d);
    }
    std::sort(m+1,m+1+n,SORTF());
    st=0;
    for(i=2 ; i<=n ; i++)
    {
        if(m[i].d==m[i-1].d && st==0)
        {
            st=i-1;
        }
        ed=i-1;
        if(m[i].d!=m[i-1].d)
        {
            std::sort(m+1+st,m+1+ed,sortf());
            st=0;
        }
    }
    for(i=1 ; i<=n ; i++)
    {
        dist[i]=abs(m[i].t-m[i].d)+l;
    }
    return 0;
}

int dp()
{
    int i, j;
    for(i=1 ; i<=n ; i++)
    {
        for(j=i-1 ; j>=0 ; j--)
        {
            if(j==0)
            {
                if(td[i]==0) td[i]=dist[i];
                if(dd[i]==0) dd[i]=dist[i];
            }
            if(m[i].t==m[j].t && dd[j]+dist[i]>td[i] && m[i].d>m[j].d)
            {
                td[i]=dd[j]+dist[i];
            }
            if(m[i].d==m[j].d && td[j]+dist[i]>td[i] && m[i].t>m[j].t)
            {
                dd[i]=td[j]+dist[i];
            }
        }
        if(td[i]>max) max=td[i];
        if(dd[i]>max) max=dd[i];
    }
    return 0;
}

int output()
{
    printf("%lld",max);
    return 0;
}

int main()
{
    input();
    dp();
    output();
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 22
• Subtask 5: 0 / 38