oj.uz

Submission #885135

# Submission time Handle Problem Language Result Execution time Memory
885135 2023-12-09T04:07:02 Z rukashii Triple Jump (JOI19_jumps) C++17
19 / 100
 369 ms 172252 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 0 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 5 ms 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 5 ms 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 369 ms 172224 KB Output is correct
12 Correct 331 ms 172088 KB Output is correct
13 Correct 327 ms 172116 KB Output is correct
14 Correct 329 ms 172116 KB Output is correct
15 Correct 325 ms 172252 KB Output is correct
16 Correct 337 ms 171740 KB Output is correct
17 Correct 335 ms 171396 KB Output is correct
18 Correct 337 ms 171476 KB Output is correct
19 Correct 324 ms 171888 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 5 ms 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 369 ms 172224 KB Output is correct
12 Correct 331 ms 172088 KB Output is correct
13 Correct 327 ms 172116 KB Output is correct
14 Correct 329 ms 172116 KB Output is correct
15 Correct 325 ms 172252 KB Output is correct
16 Correct 337 ms 171740 KB Output is correct
17 Correct 335 ms 171396 KB Output is correct
18 Correct 337 ms 171476 KB Output is correct
19 Correct 324 ms 171888 KB Output is correct
20 Incorrect 14 ms 2396 KB Output isn't correct
21 Halted 0 ms 0 KB -