Submission #557669

#TimeUsernameProblemLanguageResultExecution timeMemory
557669n0sk1llWatching (JOI13_watching)C++14
100 / 100
294 ms16036 KiB
#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 (stderr)

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];
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...