oj.uz

Submission #955805

# Submission time Handle Problem Language Result Execution time Memory
955805 2024-03-31T12:37:44 Z vjudge1 Sparklers (JOI17_sparklers) C++17
30 / 100
 2000 ms 8536 KB 
#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const long long maxn=1000+10;
const long long logn=25;

long long n,k,t;
long long x[maxn];
long long dp[maxn][maxn];
long long kol=0;

long long f(long long L,long long R)
{
    if(L==0 && R==n-1)
    {
        return true;
    }
    long long rez=0;
    if(R<n-1 && (x[R+1]-x[L])<=(R-L+1)*t*(2*kol))
    {
        rez=max(rez,f(L,R+1));
    }
    if(L>0 && (x[R]-x[L-1])<=(R-L+1)*t*(2*kol))
    {
        rez=max(rez,f(L-1,R));
    }
    return rez;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>t;
    k--;
    memset(dp,-1,sizeof dp);
    for(long long i=0;i<n;i++)
    {
        cin>>x[i];
    }
    long long l=0;
    long long r=x[n-1]-x[0];
    long long ans=0;
    while(l<=r)
    {
        long long mid=l+(r-l)/2;
        kol=mid;
        if(f(k,k))
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans<<endl;

    /*long long m,n;
    cin>>m>>n;
    long long mi=2e9;
    long long mx=-1;
    vector<pair<pair<long long,long long>,pair<long long,long long>>>p;
    vector<pair<pair<long long,long long>,pair<long long,long long>>>x;
    for(long long i=0;i<m;i++)
    {
        long long a,b,c,d;
        cin>>a>>b>>c>>d;
        p.push_back({{a,b},{c,d}});
        mi=min(mi,a);
        mx=max(mx,b);
    }
    n=mx-mi+1;
    map<long long,long long>m;
    long long cnt=0;
    for(long long i=mi;i<=mx;i++)
    {
        m[i]=cnt;
        cnt++;
    }
    for(long long i=0;i<m;i++)
    {
        long long a=p.first.first;
        long long b=p.first.second;
        long long c=p.second.first;
        long long d=p.second.second;
        x.push_back({{m[a],m[b]},{m[c],m[d]}});
    }*/

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8332 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 8 ms 8448 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 3 ms 8328 KB Output is correct
16 Correct 5 ms 8448 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 6 ms 8536 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8332 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 8 ms 8448 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 3 ms 8328 KB Output is correct
16 Correct 5 ms 8448 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 6 ms 8536 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Execution timed out 2063 ms 8348 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8332 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 8 ms 8448 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 3 ms 8328 KB Output is correct
16 Correct 5 ms 8448 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 6 ms 8536 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Execution timed out 2063 ms 8348 KB Time limit exceeded
23 Halted 0 ms 0 KB -