oj.uz

Submission #4485

# Submission time Handle Problem Language Result Execution time Memory
4485 2013-10-11T07:18:29 Z ansol4328 막대기 (KOI13_game) C++
0 / 100
 1000 ms 4216 KB 
#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)
        {
            st=0;
            std::sort(m+1+st,m+1+ed,sortf());
        }
    }
    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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4216 KB Output is correct
2 Incorrect 0 ms 4216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 4212 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 4212 KB Program timed out
2 Halted 0 ms 0 KB -