Submission #1100343

#TimeUsernameProblemLanguageResultExecution timeMemory
1100343baoquanTriple Jump (JOI19_jumps)C++14
0 / 100
2 ms336 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 5e3 + 4; const int maxm = 5e3 + 4; int a[maxn] , n , m , dp[maxm][maxm] , ma[maxm][maxm]; int l[maxn] , r[maxn]; void nhap() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen("CHONQUA.INP" , "r" , stdin); freopen("CHONQUA.OUT" , "w" , stdout); cin >> n; for (int i = 1 ; i <= n ; i ++) cin >> a[i]; cin >> m; for (int i = 1 ; i <= m ; i ++) cin >> l[i] >> r[i]; } void xl1(int l , int r) { int ans = 0; for (int i = l ; i <= r - 2 ; i ++) { for (int j = i + 1 ; j <= r - 1 ; j ++) { for (int k = j + (j - i) ; k <= r ; k ++) { ans = max(ans , a[i] + a[j] + a[k]); } } } cout << ans << '\n'; } void Sub1() { for (int i = 1 ; i <= m ; i ++) { xl1(l[i] , r[i]); } } void Sub2() { for (int i = 1 ; i <= n ; i ++) ma[i][i] = a[i]; for (int i = 1 ; i < n ; i ++) for (int j = i + 1 ; j <= n ; j ++) { ma[i][j] = max(ma[i][j - 1] , a[j]); } // for (int i = 1 ; i <= n ; i ++) // dp[i][i] = 0; // for (int i = 1 ; i < n ; i ++) // dp[i][i + 1] = 0; for (int i = 2 ; i < n ; i ++) { for (int j = 1 ; j <= n - i ; j ++) { dp[j][j + i] = max(dp[j][j + i - 1] , max(dp[j + 1][j + i] , a[j] + a[j + i] + ma[j + 1][(j + i + 1) / 2])); } } for (int i = 1 ; i <= m ; i ++) { cout << dp[l[i]][r[i]] << '\n'; } } signed main() { nhap(); if (n <= 100 && m <= 100) Sub1(); else if (n <= 5000) Sub2(); }

Compilation message (stderr)

jumps.cpp: In function 'void nhap()':
jumps.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("CHONQUA.INP" , "r" , stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("CHONQUA.OUT" , "w" , stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...