Submission #260508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
260508	2020-08-10T12:09:24 Z	stefantaga	Global Warming (CEOI18_glo)	C++14	28 / 100	2000 ms	4972 KB

glo

#include <bits/stdc++.h>

using namespace std;
int n,x,i,v[200005],b[200005],poz,lcresc[200005],ldesc[200005],j,maxim;
int caut (int val)
{
    int st=1,dr=n,mij,sol=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (b[mij]<val)
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return sol;
}
int caut1 (int val)
{
    int st=1,dr=n,mij,sol=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (b[mij]>val)
        {
            dr=mij-1;
        }
        else
        {
            sol=mij;
            st=mij+1;
        }
    }
    return sol;
}
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>x;
    for (i=1;i<=n;i++)
    {
        b[i]=2000000005;
    }
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        poz=caut(v[i]);
        if (v[i]<b[poz+1])
        {
            b[poz+1]=v[i];
            lcresc[i]=poz+1;
        }
    }
    for (i=1;i<=n;i++)
    {
        b[i]=-2000000005;
    }
    for (i=n;i>=1;i--)
    {
        ldesc[i]=1;
        for (j=i+1;j<=n;j++)
        {
            if (v[i]<v[j])
            {
                ldesc[i]=max(ldesc[i],ldesc[j]+1);
            }
        }
    }
    maxim=1;
    for (i=1;i<=n;i++)
    {
        for (j=i-1;j>=1;j--)
        {
             if (v[j]-x<v[i])
             {
                 maxim=max(maxim,ldesc[i]+lcresc[j]);
             }
        }
    }
    cout<<maxim<<'\n';
    return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	416 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	416 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	416 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	4 ms	384 KB	Output is correct
23	Correct	3 ms	384 KB	Output is correct
24	Correct	3 ms	384 KB	Output is correct
25	Correct	3 ms	384 KB	Output is correct
26	Correct	4 ms	384 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2081 ms	4972 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2071 ms	1764 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2077 ms	2852 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	416 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	4 ms	384 KB	Output is correct
23	Correct	3 ms	384 KB	Output is correct
24	Correct	3 ms	384 KB	Output is correct
25	Correct	3 ms	384 KB	Output is correct
26	Correct	4 ms	384 KB	Output is correct
27	Execution timed out	2081 ms	4972 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-