Submission #419370

#	Time	Username	Problem	Language	Result	Execution time	Memory
419370		juggernaut	Watching (JOI13_watching)	C++17	100 / 100	715 ms	16096 KiB

watching

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n,x,y;
int a[2005];
int dp[2005][2005];
int nxt(int id,int len){
    if(id>n)return n;
    if(a[n]-a[id]+1<=len)return n;
    int l=id,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(a[mid]-a[id]+1<=len)l=mid;
        else r=mid-1;
    }
    return l;
}
bool check(int w){
    memset(dp,0,sizeof dp);
    for(int i=0;i<=x;i++)
    for(int j=0;j<=y;j++)dp[i][j]=max(i?nxt(dp[i-1][j]+1,w):0,j?nxt(dp[i][j-1]+1,w<<1):0);
    return dp[x][y]==n;
}
int main(){
    scanf("%d%d%d",&n,&x,&y);
    umin(y,n);
    umin(x,n-y);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int l=1,r=5e8;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",l);
}

Compilation message (stderr)

watching.cpp: In function 'void usaco(std::string)':
watching.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp: In function 'int main()':
watching.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d%d%d",&n,&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:44:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50