oj.uz

Submission #77435

# Submission time Handle Problem Language Result Execution time Memory
77435 2018-09-27T20:07:20 Z Vardanyan Watching (JOI13_watching) C++14
50 / 100
 247 ms 64436 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 201;
int a[N];
int mxshort[N];
int mxlong[N];
int dp[N][N][N];
int main(){
    int n,p,q;
    scanf("%d%d%d",&n,&p,&q);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int l = 1;
    int r = 1000*1000*1000;
    int ans = r;
    while(l<=r){
        int m = (l+r)/2;
        memset(mxlong,0,sizeof(mxlong));
        memset(mxshort,0,sizeof(mxshort));
        memset(dp,0,sizeof(dp));
        int now = n;
        int noww = n;
        for(int i = n;i>=1;i--){
            while(!(abs(a[i]-a[now])+1<=m)) now--;
            mxshort[i] = now;
            while(!(abs(a[i]-a[noww])+1<=2*m)) noww--;
            mxlong[i] = noww;
        }
        bool f = false;
        for(int i = 1;i<=n+1;i++){
            for(int j = 0;j<=min(100,p);j++){
                for(int k = 0;k<=min(100,q);k++){
                    if(i == 1 || dp[i][j][k]){
                        if(i == n+1 && (j<=p && k<=q)){
                            f = true;
                            break;
                        }
                        dp[mxshort[i]+1][j+1][k] = dp[mxlong[i]+1][j][k+1] = 1;
                    }
                }
                if(f) break;
            }
            if(f) break;
        }
        if(f){
            ans = m;
            r = m-1;
        }
        else l = m+1;
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&p,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:11:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     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 166 ms 32120 KB Output is correct
2 Correct 149 ms 32252 KB Output is correct
3 Correct 166 ms 32328 KB Output is correct
4 Correct 176 ms 32388 KB Output is correct
5 Correct 168 ms 32388 KB Output is correct
6 Correct 247 ms 32396 KB Output is correct
7 Correct 149 ms 32448 KB Output is correct
8 Correct 177 ms 32448 KB Output is correct
9 Correct 166 ms 32448 KB Output is correct
10 Correct 165 ms 32448 KB Output is correct
11 Correct 180 ms 32448 KB Output is correct
12 Correct 198 ms 32448 KB Output is correct
13 Correct 149 ms 32448 KB Output is correct
14 Correct 165 ms 32448 KB Output is correct
15 Correct 174 ms 32452 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 64436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -