제출 #892520

#제출 시각아이디문제언어결과실행 시간메모리
892520LeVanThucBigger segments (IZhO19_segments)C++17
0 / 100
5 ms27228 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> #define kt cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n" template<class T1,class T2> bool maximize(T1 &x,T2 y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,T2 y) { if(y<x) { x=y; return 1; } return 0; } const ll M=1e9+7; template <class T1,class T2> void add(T1 &x,T2 y) { x+=y; if(x>=M) x-=M; } template <class T1,class T2> void sub(T1 &x, T2 y) { x-=y; if(x<0) x+=M; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.inp","r",stdin); freopen("output.out","w",stdout); #else #endif // thuc } const ll N=5e5+10,S=400; ll n,a[N],f[N]; map<ll,ll> dp[N]; int main() { online(); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]+=a[i-1]; } ll ans=1; dp[1][1]=1; f[1]=1; for(int i=1;i<=n;i++) { for(int j=f[i];j>=f[i]-1;j--) { if(j==0) continue; maximize(dp[i+1][j],dp[i][j]); maximize(f[i+1],dp[i][j]); ll z=a[i]-a[dp[i][j]-1]; ll nxt=lower_bound(a+1,a+n+1,a[i]+z)-a; maximize(dp[nxt][j+1],i+1); maximize(f[nxt],j+1); } } cout<<f[n]; kt; }

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In function 'int main()':
segments.cpp:68:8: warning: unused variable 'ans' [-Wunused-variable]
   68 |     ll ans=1;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...