oj.uz

Submission #419368

# Submission time Handle Problem Language Result Execution time Memory
419368 2021-06-07T03:56:24 Z juggernaut Watching (JOI13_watching) C++17
100 / 100
 267 ms 16088 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;
    for(int i=id;i<=n;i++)if(a[i]-a[id]+1>len)return i-1;
}
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 nxt(int, int)':
watching.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
watching.cpp: In function 'int main()':
watching.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d%d",&n,&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     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 60 ms 15948 KB Output is correct
2 Correct 62 ms 15948 KB Output is correct
3 Correct 62 ms 15948 KB Output is correct
4 Correct 61 ms 16012 KB Output is correct
5 Correct 62 ms 15912 KB Output is correct
6 Correct 63 ms 16012 KB Output is correct
7 Correct 61 ms 15952 KB Output is correct
8 Correct 62 ms 15948 KB Output is correct
9 Correct 64 ms 16088 KB Output is correct
10 Correct 60 ms 16012 KB Output is correct
11 Correct 62 ms 16012 KB Output is correct
12 Correct 62 ms 16012 KB Output is correct
13 Correct 59 ms 15948 KB Output is correct
14 Correct 63 ms 16012 KB Output is correct
15 Correct 63 ms 16016 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16036 KB Output is correct
2 Correct 61 ms 15948 KB Output is correct
3 Correct 221 ms 16052 KB Output is correct
4 Correct 97 ms 15948 KB Output is correct
5 Correct 62 ms 15948 KB Output is correct
6 Correct 62 ms 15948 KB Output is correct
7 Correct 63 ms 16040 KB Output is correct
8 Correct 96 ms 16032 KB Output is correct
9 Correct 98 ms 15960 KB Output is correct
10 Correct 106 ms 15948 KB Output is correct
11 Correct 98 ms 15948 KB Output is correct
12 Correct 267 ms 16028 KB Output is correct
13 Correct 62 ms 15948 KB Output is correct
14 Correct 60 ms 16032 KB Output is correct
15 Correct 63 ms 15948 KB Output is correct