oj.uz

Submission #885134

# Submission time Handle Problem Language Result Execution time Memory
885134 2023-12-09T04:06:43 Z rukashii Triple Jump (JOI19_jumps) C++17
19 / 100
 390 ms 177036 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4952 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4952 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 390 ms 177036 KB Output is correct
12 Correct 377 ms 176708 KB Output is correct
13 Correct 385 ms 176884 KB Output is correct
14 Correct 345 ms 176964 KB Output is correct
15 Correct 341 ms 176720 KB Output is correct
16 Correct 369 ms 176252 KB Output is correct
17 Correct 349 ms 176152 KB Output is correct
18 Correct 341 ms 176212 KB Output is correct
19 Correct 331 ms 176860 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4952 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 390 ms 177036 KB Output is correct
12 Correct 377 ms 176708 KB Output is correct
13 Correct 385 ms 176884 KB Output is correct
14 Correct 345 ms 176964 KB Output is correct
15 Correct 341 ms 176720 KB Output is correct
16 Correct 369 ms 176252 KB Output is correct
17 Correct 349 ms 176152 KB Output is correct
18 Correct 341 ms 176212 KB Output is correct
19 Correct 331 ms 176860 KB Output is correct
20 Incorrect 14 ms 4184 KB Output isn't correct
21 Halted 0 ms 0 KB -