Submission #885225

#	Time	Username	Problem	Language	Result	Execution time	Memory
885225		rukashii	Triple Jump (JOI19_jumps)	C++17	46 / 100	373 ms	177748 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
 
#define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
// #define int long long
#define f first
#define s second
 
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
    if (s.size()) setIn(s+".inp"), setOut(s+".out");
}
 
const int maxn = 5e5 + 2;
 
int a[maxn], n, q;
 
namespace Sub1
{
    void solve()
    {
        while (q--)
        {
            int l, r, ans = 0;
            cin >> l >> r;
 
            for (int i = l; i <= r; i++)
            {
                for (int j = i + 1; j <= r; j++)
                {
                    for (int k = j + 1; k <= r; k++)
                    {
                        if (k - j >= j - i)
                        {
                            ans = max(ans, a[i] + a[j] + a[k]);
                        }
                    }
                }
            }
 
            cout << ans << '\n';
        }
    }
} // namespace Sub1
 
namespace Sub2
{
    const int s2maxn = 5002;
 
    int dp[s2maxn][s2maxn], mx[s2maxn][s2maxn];
    void solve()
    {
        for (int i = 1; i <= n; i++)
        {
            mx[i][i] = a[i];
        }
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                mx[i][j] = max(mx[i][j - 1], a[j]);
            }
        }
 
        for (int sz = 3; sz <= n; sz++)
        {
            for (int i = 1; i + sz - 1 <= n; i++)
            {
                int l = i, r = i + sz - 1;
                // if (sz == 3 && i == 1)
                    // cout << l << ' ' << r << ' ' << (l + r) / 2 << ' ' << mx[l][(l + r) / 2] << '\n';
                dp[l][r] = max({dp[l + 1][r], dp[l][r - 1], a[l] + a[r] + mx[l + 1][(l + r) / 2]});
            }
        }
 
        while (q--)
        {
            int l, r;
            cin >> l >> r;
 
            cout << dp[l][r] << '\n';
        }
    }
} // namespace Sub2
 
 namespace Sub3
 {
    int prf[maxn];

    void solve()
    {
        stack <int> st;
        for (int i = 1; i <= n; i++)
        {
            while (st.size() && a[st.top()] < a[i])
            {
                if (i + (i - st.top() + 1) - 1 <= n)
                    prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]);
                
                st.pop();
            }

            if (st.size())
                if (i + (i - st.top() + 1) - 1 <= n)
                    prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]);
            st.push(i);
        }

        for (int i = 1; i <= n; i++)
        {
            prf[i] = max(prf[i - 1], prf[i]);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ans = max(ans, prf[i] + a[i]);
        }

        cout << ans << '\n';
    }
 } // namespace Sub3
 
 
signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0); cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++)    
        cin >> a[i];
 
    cin >> q;
    if (n <= 100)
    {
        return Sub1::solve(), 0;
    }
    if (n <= 5000)
    {
        return Sub2::solve(), 0;
    }
    if (q == 1)
    {
        return Sub3::solve(), 0;
    }
}

Compilation message (stderr)

jumps.cpp: In function 'void setIn(std::string)':
jumps.cpp:9:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void setOut(std::string)':
jumps.cpp:10:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:4:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:129:5: note: in expansion of macro 'file'
  129 |     file;
      |     ^~~~
jumps.cpp:4:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:129:5: note: in expansion of macro 'file'
  129 |     file;
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54