oj.uz

Submission #870145

# Submission time Handle Problem Language Result Execution time Memory
870145 2023-11-07T04:18:59 Z Eliorita Watching (JOI13_watching) C++14
100 / 100
 295 ms 32088 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int n,a,b,A[N],dp[2001][2001],ans,l=1,r=1e9+8;
bool check(int x)
{
    int mn=LLONG_MAX;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=1;
        while(l<i&&A[i]>=x+A[l]) l++;
        for(int j=0;j<=b;j++) dp[i][j]=dp[l-1][j]+1;
        while(r<i&&A[i]>=2*x+A[r]) r++;
        for(int j=0;j<=b;j++) dp[i][j+1]=min(dp[i][j+1],dp[r-1][j]);
    }
    for(int i=0;i<=b;i++) mn=min(mn,dp[n][i]);
    return mn<=a;
}
signed main()
{
    if(fopen("paint.inp","r"))
    {
        freopen("paint.inp","r",stdin);
        freopen("paint.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b;
    if(n<=a+b) {cout<<1; return 0;}
    for(int i=1;i<=n;i++) cin>>A[i];
    sort(A+1,A+n+1);
    while(l<=r)
    {
        int m=(l+r)/2;
        if(check(m))
        {
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    cout<<ans;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("paint.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("paint.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 31776 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 67 ms 31780 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 69 ms 31784 KB Output is correct
8 Correct 66 ms 31780 KB Output is correct
9 Correct 68 ms 31784 KB Output is correct
10 Correct 68 ms 31576 KB Output is correct
11 Correct 67 ms 31580 KB Output is correct
12 Correct 66 ms 31580 KB Output is correct
13 Correct 67 ms 31784 KB Output is correct
14 Correct 66 ms 31784 KB Output is correct
15 Correct 65 ms 31780 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 32088 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 476 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 111 ms 31660 KB Output is correct
8 Correct 196 ms 31832 KB Output is correct
9 Correct 131 ms 31836 KB Output is correct
10 Correct 127 ms 31832 KB Output is correct
11 Correct 295 ms 31812 KB Output is correct
12 Correct 217 ms 31836 KB Output is correct
13 Correct 107 ms 31836 KB Output is correct
14 Correct 115 ms 31832 KB Output is correct
15 Correct 114 ms 31580 KB Output is correct