oj.uz

Submission #4488

# Submission time Handle Problem Language Result Execution time Memory
4488 2013-10-11T08:26:42 Z ansol4328 막대기 (KOI13_game) C++
49 / 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+1 ; i++)
    {
        if(m[i].t==m[i-1].t && st==0)
        {
            st=i-1;
        }
        ed=i-1;
        if(m[i].t!=m[i-1].t)
        {
            std::sort(m+st,m+1+ed,sortf());
            st=i;
        }
    }
    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 && td[j]+dist[i]>dd[i] && m[i].d>m[j].d)
            {
                dd[i]=td[j]+dist[i];
            }
            if(m[i].d==m[j].d && dd[j]+dist[i]>td[i] && m[i].t>m[j].t)
            {
                td[i]=dd[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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4216 KB Output is correct
2 Correct 0 ms 4216 KB Output is correct
3 Correct 0 ms 4216 KB Output is correct
4 Correct 0 ms 4216 KB Output is correct
5 Correct 0 ms 4216 KB Output is correct

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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4216 KB Output is correct
2 Correct 0 ms 4216 KB Output is correct
3 Correct 0 ms 4216 KB Output is correct
4 Correct 0 ms 4216 KB Output is correct
5 Correct 0 ms 4216 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4216 KB Output is correct
2 Correct 0 ms 4216 KB Output is correct
3 Correct 0 ms 4216 KB Output is correct
4 Correct 0 ms 4216 KB Output is correct
5 Correct 0 ms 4216 KB Output is correct
6 Correct 0 ms 4216 KB Output is correct
7 Correct 0 ms 4216 KB Output is correct

Subtask #5
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4216 KB Output is correct
2 Correct 96 ms 4216 KB Output is correct
3 Execution timed out 1000 ms 4212 KB Program timed out
4 Halted 0 ms 0 KB -