Submission #885134

#	Time	Username	Problem	Language	Result	Execution time	Memory
885134		rukashii	Triple Jump (JOI19_jumps)	C++17	19 / 100	390 ms	177036 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



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;
    }
}

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:93:5: note: in expansion of macro 'file'
   93 |     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:93:5: note: in expansion of macro 'file'
   93 |     file;
      |     ^~~~

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