oj.uz

Submission #419370

# Submission time Handle Problem Language Result Execution time Memory
419370 2021-06-07T04:00:54 Z juggernaut Watching (JOI13_watching) C++17
100 / 100
 715 ms 16096 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15980 KB Output is correct
2 Correct 63 ms 16016 KB Output is correct
3 Correct 63 ms 15948 KB Output is correct
4 Correct 65 ms 15948 KB Output is correct
5 Correct 61 ms 15948 KB Output is correct
6 Correct 63 ms 15944 KB Output is correct
7 Correct 61 ms 16020 KB Output is correct
8 Correct 66 ms 15948 KB Output is correct
9 Correct 62 ms 15948 KB Output is correct
10 Correct 66 ms 15948 KB Output is correct
11 Correct 63 ms 15948 KB Output is correct
12 Correct 68 ms 15948 KB Output is correct
13 Correct 63 ms 15948 KB Output is correct
14 Correct 63 ms 15948 KB Output is correct
15 Correct 64 ms 15948 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 15948 KB Output is correct
2 Correct 61 ms 15948 KB Output is correct
3 Correct 534 ms 16012 KB Output is correct
4 Correct 163 ms 16016 KB Output is correct
5 Correct 64 ms 16008 KB Output is correct
6 Correct 63 ms 15976 KB Output is correct
7 Correct 65 ms 15948 KB Output is correct
8 Correct 161 ms 16012 KB Output is correct
9 Correct 178 ms 16012 KB Output is correct
10 Correct 182 ms 16012 KB Output is correct
11 Correct 183 ms 16096 KB Output is correct
12 Correct 715 ms 16012 KB Output is correct
13 Correct 64 ms 15948 KB Output is correct
14 Correct 64 ms 15948 KB Output is correct
15 Correct 66 ms 16012 KB Output is correct