제출 #689420

#제출 시각아이디문제언어결과실행 시간메모리
689420Matteo_VerzBigger segments (IZhO19_segments)C++17
13 / 100
1 ms212 KiB
#include <bits/stdc++.h> #ifdef BLAT #include "debug/debug.hpp" #else #define debug(x...) #endif using namespace std; const long long INF = 1'000'000'000'000'000; // 1e15 int binSearch(const vector <long long> &v, int val) { int r, pas; for (r = -1, pas = 1 << 17; pas; pas >>= 1) if (r + pas < v.size() && v[r + pas] < val) r += pas; r++; return r; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector <int> v(1 + n), dp(1 + n); vector <long long> sp(1 + n), s(1 + n, INF); for (int i = 1; i <= n; i++) { cin >> v[i]; sp[i] = sp[i - 1] + v[i]; } dp[1] = 1; s[1] = sp[1]; for (int i = 1; i <= n; i++) { dp[i] = max(dp[i], dp[i - 1]); s[i] = min(s[i], s[i - 1] + v[i]); int pos = binSearch(sp, s[i] + sp[i]); if (pos == n + 1) continue; if (dp[pos] == dp[i] + 1) s[pos] = min(s[pos], sp[pos] - sp[i]); else if (dp[pos] < dp[i] + 1) { s[pos] = sp[pos] - sp[i]; dp[pos] = 1 + dp[i]; } } cout << dp[n] << '\n'; return 0; }

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

segments.cpp: In function 'int binSearch(const std::vector<long long int>&, int)':
segments.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if (r + pas < v.size() && v[r + pas] < val)
      |             ~~~~~~~~^~~~~~~~~~
#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...