Submission #1118074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118074		cpdreamer	Watching (JOI13_watching)	C++17	50 / 100	1002 ms	6376 KiB

watching

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair
#define S second
#define F first
#define all(v) v.begin(),v.end()
#define V vector
#define pb push_back
const ll MOD=998244353;
void file() {
    freopen("input.txt.txt", "r", stdin);
    freopen("output.txt.txt", "w", stdout);
}
void setIO(string s = "") {
    if (!s.empty()){
        freopen((s + ".in").c_str(), "r", stdin);
        freopen((s + ".out").c_str(), "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
}
long long intersection(const std::pair<long long, long long>& interval1,
                       const std::pair<long long, long long>& interval2) {
    long long start = std::max(interval1.first, interval2.first);
    long long end = std::min(interval1.second, interval2.second);
    if (start <= end) {
        return end - start + 1;
    }
    return 0;
}
int find(int A[],int n,int right,int v){
    int ans=-1;
    if(v<A[1])
        return 0;
    int l=1,r=right;
    while(l<=r){
        int m=l+(r-l)/2;
        if(A[m]<=v){
            ans=m;
            l=m+1;
        }
        else
            r=m-1;
    }
    if(ans==-1)
        return 0;
    return ans;
}
void solve() {
    int n,p,q;
    cin>>n>>p>>q;
    int A[n+1];
    for(int i=1;i<=n;i++)
        cin>>A[i];
    if(p+q>=n){
        cout<<1<<endl;
        return;
    }
    sort(A+1,A+n+1);
    int l=1,r=1e9;
    int ans=-1;
    while(l<=r){
        int m=l+(r-l)/2;
        int w=m;
        int dp[n+1][q+1];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=q;j++){
                dp[i][j]=1e9;
                int last=find(A,n,i-1,A[i]-w);
                dp[i][j]=min(dp[i][j],dp[last][j]+1);
                if(j>=1){
                    last=find(A,n,i-1,A[i]-2*w);
                    dp[i][j]=min(dp[i][j],dp[last][j-1]);
                }
            }
        }
        if(dp[n][q]<=p){
            ans=w;
            r=m-1;
        }
        else
            l=m+1;
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //file();
    solve();
}

Compilation message (stderr)

watching.cpp: In function 'void file()':
watching.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen("input.txt.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("output.txt.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp: In function 'void setIO(std::string)':
watching.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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