oj.uz

Submission #492598

# Submission time Handle Problem Language Result Execution time Memory
492598 2021-12-08T05:35:06 Z ToroTN Watching (JOI13_watching) C++14
100 / 100
 910 ms 16524 KB 
#include<bits/stdc++.h>
using namespace std;
int n,p,q,a,st,md,ed,dp[2005][2005],val,idx,st1,st2,type;
vector<int> small[2005],large[2005],v;
int main()
{
    scanf("%d%d%d",&n,&p,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    st=1;
    ed=1e9;
    while(ed>=st)
    {
        md=(st+ed)/2;
        //printf("%d %d %d\n",st,md,ed);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                dp[i][j]=1e9;
            }
        }
        md=(st+ed)/2;
        for(int i=0;i<v.size()-1;i++)
        {
            val=v[i+1]+md-1;
            idx=upper_bound(v.begin(),v.end(),val)-v.begin()-1;
            //printf("%d %d\n",i,idx);
            small[idx].push_back(i);
        }
        //printf("\n");
        for(int i=0;i<v.size()-1;i++)
        {
            val=v[i+1]+2*md-1;
            idx=upper_bound(v.begin(),v.end(),val)-v.begin()-1;
            //printf("%d %d\n",i,idx);
            large[idx].push_back(i);
        }
        //printf("\n");
        st1=upper_bound(v.begin(),v.end(),v[0]+md-1)-v.begin()-1;
        st2=upper_bound(v.begin(),v.end(),v[0]+2*md-1)-v.begin()-1;
        //printf("%d %d\n",st1,st2);
        dp[st1][1]=min(dp[st1][1],0);
        dp[st2][0]=min(dp[st2][0],1);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<small[i].size();k++)
                {
                    if(j>0)
                    {
                        dp[i][j]=min(dp[i][j],dp[small[i][k]][j-1]);
                    }
                }
                for(int k=0;k<large[i].size();k++)
                {
                    dp[i][j]=min(dp[i][j],dp[large[i][k]][j]+1);
                }
            }
        }
        type=-1;
        for(int i=0;i<=min(p,2000);i++)
        {
            if(dp[n-1][i]<=q)
            {
                type=0;
            }
        }
        if(type==0)
        {
            ed=md-1;
        }else
        {
            st=md+1;
        }
        for(int i=0;i<n;i++)
        {
            small[i].clear();
            large[i].clear();
        }
    }
    //printf("%d %d %d\n",st,md,ed);
    printf("%d\n",st);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i=0;i<v.size()-1;i++)
      |                     ~^~~~~~~~~~~
watching.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0;i<v.size()-1;i++)
      |                     ~^~~~~~~~~~~
watching.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 for(int k=0;k<small[i].size();k++)
      |                             ~^~~~~~~~~~~~~~~~
watching.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 for(int k=0;k<large[i].size();k++)
      |                             ~^~~~~~~~~~~~~~~~
watching.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%d%d%d",&n,&p,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 844 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 4 ms 828 KB Output is correct
15 Correct 2 ms 716 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 16204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 678 ms 16348 KB Output is correct
4 Correct 637 ms 16516 KB Output is correct
5 Correct 600 ms 16300 KB Output is correct
6 Correct 593 ms 16524 KB Output is correct
7 Correct 834 ms 16228 KB Output is correct
8 Correct 721 ms 16512 KB Output is correct
9 Correct 672 ms 16344 KB Output is correct
10 Correct 670 ms 16272 KB Output is correct
11 Correct 583 ms 16428 KB Output is correct
12 Correct 604 ms 16520 KB Output is correct
13 Correct 799 ms 16232 KB Output is correct
14 Correct 607 ms 16232 KB Output is correct
15 Correct 573 ms 16232 KB Output is correct