oj.uz

답안 #1006393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006393 2024-06-24T00:48:07 Z kebine Bigger segments (IZhO19_segments) C++17
0 / 100
 0 ms 348 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[500005], pos[500005], pref[500005], a[500005];
int main()
{
  ll n;
  scanf("%lld", &n);
  for(int i=1; i<=n; i++)
  {
    scanf("%lld", &a[i]);
    pref[i]=pref[i-1]+a[i];
  }
  pref[n+1]=1e18;
  for(int i=1; i<=n; i++)
  {
    dp[i]=dp[pos[i]]+1;
    pos[i]=max(pos[i], pos[i-1]);
    ll pt=lower_bound(pref+1, pref+n+1, 2*pref[i]-pref[max(pos[i], pos[i]-1)])-pref;
//    printf("pos=%lld %lld %lld\n", pos[i], pt, dp[i]);
    pos[pt]=i;
  }
  printf("%lld\n", dp[n]);
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   scanf("%lld", &n);
      |   ~~~~~^~~~~~~~~~~~
segments.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -