제출 #942712

#제출 시각아이디문제언어결과실행 시간메모리
942712penguin1333단 점프 (JOI19_jumps)C++17
19 / 100
4477 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, A[500005], S[500005], q; int ans; void dnc(int l, int r, int optl, int optr){ if(l > r)return; int mid = (l + r) >> 1; int mx = -1e18, opt = max(optl, mid * 2 - n); for(int i = max(optl, mid * 2 - n); i <= min(optr, mid - 1); i++){ if(A[i] + A[mid] + S[mid * 2 - i] > mx){ mx = A[i] + A[mid] + S[mid * 2 - i]; opt = i; } } ans = max(ans, mx); dnc(l, mid - 1, optl, opt); dnc(mid + 1, r, opt, optr); } int memo[5005][5005], bru[5005][5005]; void solve(){ cin >> n; for(int i = 1; i <= n; i++)cin >> A[i]; for(int i = 1; i <= n; i++){ bru[i][i] = A[i]; for(int j = i + 1; j <= n; j++)bru[i][j] = max(A[j], bru[i][j - 1]); } for(int i = 1; i <= n - 2; i++)memo[i][i + 2] = A[i] + A[i + 1] + A[i + 2]; for(int i = 3; i < n; i++){ for(int j = 1; j <= n - i; j++){ memo[j][j + i] = max({memo[j][j + i - 1], memo[j + 1][j + i], A[j + i] + A[j] + bru[j + 1][(i + j + j) / 2]}); } } S[n] = A[n]; for(int i = n - 1; i >= 1; i--)S[i] = max(S[i + 1], A[i]); cin >> q; while(q--){ int l, r; cin >> l >> r; cout << memo[l][r] << '\n'; } //dnc(1, n, 1, n); //cout << ans; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

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

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