oj.uz

Submission #557669

# Submission time Handle Problem Language Result Execution time Memory
557669 2022-05-05T18:21:53 Z n0sk1ll Watching (JOI13_watching) C++14
100 / 100
 294 ms 16036 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;

/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/







//Note to self: Check for overflow

int a[2005];
int dp[2005][2005];

bool moze(int w, int n, int p, int q)
{
    int pp=0,qq=0;
    fff(i,0,n) fff(j,0,p) dp[i][j]=1e9;
    dp[0][0]=0;
    fff(i,1,n)
    {
        while (a[i]-a[pp+1]+1>w) ++pp;
        while (a[i]-a[qq+1]+1>2*w) ++qq;
        fff(j,1,p) dp[i][j]=min(dp[i][j],dp[pp][j-1]);
        fff(j,0,p) dp[i][j]=min(dp[i][j],dp[qq][j]+1);
    }
    fff(i,0,p) if (dp[n][i]<=q) return true;
    return false;
}

int main()
{
    FAST;

    int n,p,q; cin>>n>>p>>q;
    if (p>n) p=n; if (q>n) q=n;
    fff(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);

    int l=0,r=1e9;
    while (r-l>1)
    {
        int mid=(l+r)/2;
        if (moze(mid,n,p,q)) r=mid;
        else l=mid;
    }

    cout<<r<<"\n";
}

//Note to self: Check for overflow

Compilation message

watching.cpp: In function 'bool moze(int, int, int, int)':
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:53:5: note: in expansion of macro 'fff'
   53 |     fff(i,0,n) fff(j,0,p) dp[i][j]=1e9;
      |     ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:53:16: note: in expansion of macro 'fff'
   53 |     fff(i,0,n) fff(j,0,p) dp[i][j]=1e9;
      |                ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:55:5: note: in expansion of macro 'fff'
   55 |     fff(i,1,n)
      |     ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:59:9: note: in expansion of macro 'fff'
   59 |         fff(j,1,p) dp[i][j]=min(dp[i][j],dp[pp][j-1]);
      |         ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:60:9: note: in expansion of macro 'fff'
   60 |         fff(j,0,p) dp[i][j]=min(dp[i][j],dp[qq][j]+1);
      |         ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:62:5: note: in expansion of macro 'fff'
   62 |     fff(i,0,p) if (dp[n][i]<=q) return true;
      |     ^~~
watching.cpp: In function 'int main()':
watching.cpp:71:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   71 |     if (p>n) p=n; if (q>n) q=n;
      |     ^~
watching.cpp:71:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   71 |     if (p>n) p=n; if (q>n) q=n;
      |                   ^~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:72:5: note: in expansion of macro 'fff'
   72 |     fff(i,1,n) cin>>a[i];
      |     ^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8276 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 232 ms 16028 KB Output is correct
4 Correct 290 ms 16036 KB Output is correct
5 Correct 19 ms 8916 KB Output is correct
6 Correct 287 ms 16036 KB Output is correct
7 Correct 8 ms 8404 KB Output is correct
8 Correct 25 ms 9300 KB Output is correct
9 Correct 142 ms 14252 KB Output is correct
10 Correct 294 ms 16036 KB Output is correct
11 Correct 20 ms 9052 KB Output is correct
12 Correct 163 ms 16028 KB Output is correct
13 Correct 7 ms 8404 KB Output is correct
14 Correct 9 ms 8404 KB Output is correct
15 Correct 11 ms 8404 KB Output is correct