Submission #1177224

#TimeUsernameProblemLanguageResultExecution timeMemory
1177224ASN49KSparklers (JOI17_sparklers)C++20
50 / 100
12 ms1408 KiB
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() const int inf=1e9; using i64 = long long; const i64 INF=1e18; #define int long long const int N_MAX=1000; int a[N_MAX],n,k,t; bool dp[N_MAX][N_MAX]; [[gnu::optimize("O3")]][[gnu::target("avx2")]] bool test(int s) { dp[k][k]=true; std::vector<int>xx(n); for(int i=0;i<n;i++) { xx[i]=a[i]-2*s*t*i; } for(int l=n-1;l>=0;l--) { for(int r=l+1;r<n;r++) { dp[l][r]=((dp[l][r-1]|dp[l+1][r]) & (xx[r]<=xx[l])); } } //std::cout<<min[1][2]<<' '<<max[1][2]<<'\n'; return dp[0][n-1]; } main() { std::cin>>n>>k>>t; k--; for(int i=0;i<n;i++) { std::cin>>a[i]; } //std::cout<<test(100); //return 0; int st=0,dr=a[n-1],rez=-1; while(st<=dr) { int mid=(st+dr)/2; if(test(mid)) { dr=mid-1; rez=mid; } else { st=mid+1; } } assert(rez!=-1); std::cout<<rez; return 0; } /* 2 1 10 200 300 */

Compilation message (stderr)

sparklers.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...