oj.uz

Submission #474507

# Submission time Handle Problem Language Result Execution time Memory
474507 2021-09-18T15:52:28 Z Urvuk3 Watching (JOI13_watching) C++17
100 / 100
 401 ms 16524 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=2e3+1,MAXA=5e6+5,INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

ll n,m,k,p,q,x,y,z,res=INF,l,r;
string s,t;
vector<int> a;
ifstream input;
ofstream output;

#ifdef ONLINE_JUDGE
    #define input cin
    #define output cout
#endif

bool check(int w){
    int idxp=1,idxq=1;
    vector<vector<int>> dp(MAXN,vector<int>(MAXN,0)); ///dp[i][j] najmanji broj velikih kamera da bi uz pomoc njih i j kamera prekrili prvih i eventova
    for(int i=1;i<=n;i++){
        while(a[i]-a[idxp]+1>w) idxp++;
        while(a[i]-a[idxq]+1>2*w) idxq++;
        ///PRINT(idxp); PRINT(idxq);
        for(int j=0;j<=p;j++){ ///broj manjih kamera
            dp[i][j]=INF;
            if(j) dp[i][j]=dp[idxp-1][j-1];
            dp[i][j]=min(dp[i][j],dp[idxq-1][j]+1);
        }
    }
    /*
    cerr<<"dp:"<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=p;j++){
            cerr<<dp[i][j]<<" ";
        }
        cerr<<endl;
    }
    */
    ///PRINT(p);
    return dp[n][p]<=q;
}

void solve(){
    cin>>n>>p>>q; p=min(n,p); q=min(n,q);
    a.resize(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end());
    l=1,r=INF;
    while(l<=r){
        if(check(mid)){
            res=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        input.open("D:\\UROS\\Programiranje\\input.in",ios::in);
	output.open("D:\\UROS\\Programiranje\\output.out",ios::out|ios::trunc);
    #endif
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 16124 KB Output is correct
2 Correct 200 ms 16392 KB Output is correct
3 Correct 200 ms 16264 KB Output is correct
4 Correct 200 ms 16324 KB Output is correct
5 Correct 197 ms 16268 KB Output is correct
6 Correct 205 ms 16320 KB Output is correct
7 Correct 223 ms 16232 KB Output is correct
8 Correct 208 ms 16524 KB Output is correct
9 Correct 228 ms 16248 KB Output is correct
10 Correct 211 ms 16236 KB Output is correct
11 Correct 218 ms 16208 KB Output is correct
12 Correct 219 ms 16348 KB Output is correct
13 Correct 208 ms 16296 KB Output is correct
14 Correct 213 ms 16384 KB Output is correct
15 Correct 207 ms 16292 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 16204 KB Output is correct
2 Correct 202 ms 16248 KB Output is correct
3 Correct 359 ms 16284 KB Output is correct
4 Correct 387 ms 16140 KB Output is correct
5 Correct 234 ms 16244 KB Output is correct
6 Correct 401 ms 16144 KB Output is correct
7 Correct 224 ms 16396 KB Output is correct
8 Correct 240 ms 16324 KB Output is correct
9 Correct 286 ms 16140 KB Output is correct
10 Correct 391 ms 16140 KB Output is correct
11 Correct 222 ms 16200 KB Output is correct
12 Correct 321 ms 16236 KB Output is correct
13 Correct 215 ms 16288 KB Output is correct
14 Correct 221 ms 16212 KB Output is correct
15 Correct 220 ms 16504 KB Output is correct