Submission #563386

#TimeUsernameProblemLanguageResultExecution timeMemory
563386hibikiWatching (JOI13_watching)C++11
100 / 100
268 ms16016 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define f first #define s second int n,p,q,dp[2005][2005]; vector<int> v; int main() { scanf("%d %d %d",&n,&p,&q); int lst = -1; for(int i = 0; i < n; i++) { int a; scanf("%d",&a); v.pb(a); } if(p + q >= n) { printf("1\n"); return 0; } sort(v.begin(),v.end()); int l = 1, r = 1e9 + 5; while(l <= r) { int mid = (l + r) / 2; if(l == r) { printf("%d\n",l); return 0; } for(int i = 0; i < n; i++) for(int j = 0; j <= p; j++) dp[i][j] = 1e9; for(int i = 0; i < n; i++) { int po = v[i]; // use p int p_po = upper_bound(v.begin(),v.end(),po - mid) - v.begin() - 1; if(p_po == -1) dp[i][1] = 0; else for(int j = 1; j <= p; j++) { dp[i][j] = min(dp[i][j],dp[p_po][j - 1]); } // use q p_po = upper_bound(v.begin(),v.end(),po - mid * 2) - v.begin() - 1; if(p_po == -1) dp[i][0] = 1; else for(int j = 0; j <= p; j++) { dp[i][j] = min(dp[i][j],dp[p_po][j] + 1); } } bool chk = false; for(int i = 0; i <= p; i++) if(dp[n - 1][i] <= q) { chk = true; break; } if(chk) r = mid; else l = mid + 1; } return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:14:9: warning: unused variable 'lst' [-Wunused-variable]
   14 |     int lst = -1;
      |         ^~~
watching.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d %d",&n,&p,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
watching.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...