oj.uz

Submission #885225

# Submission time Handle Problem Language Result Execution time Memory
885225 2023-12-09T10:05:42 Z rukashii Triple Jump (JOI19_jumps) C++17
46 / 100
 373 ms 177748 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
 
 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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2512 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 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 4 ms 2396 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 1 ms 2396 KB Output is correct
2 Correct 3 ms 2512 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 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 4 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 356 ms 177744 KB Output is correct
12 Correct 361 ms 177748 KB Output is correct
13 Correct 344 ms 177744 KB Output is correct
14 Correct 355 ms 177704 KB Output is correct
15 Correct 361 ms 177688 KB Output is correct
16 Correct 347 ms 177088 KB Output is correct
17 Correct 341 ms 177424 KB Output is correct
18 Correct 373 ms 177132 KB Output is correct
19 Correct 357 ms 177648 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4800 KB Output is correct
2 Correct 19 ms 4944 KB Output is correct
3 Correct 17 ms 5808 KB Output is correct
4 Correct 19 ms 4936 KB Output is correct
5 Correct 20 ms 4924 KB Output is correct
6 Correct 16 ms 4188 KB Output is correct
7 Correct 15 ms 4180 KB Output is correct
8 Correct 15 ms 4272 KB Output is correct
9 Correct 16 ms 4444 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2512 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 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 4 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 356 ms 177744 KB Output is correct
12 Correct 361 ms 177748 KB Output is correct
13 Correct 344 ms 177744 KB Output is correct
14 Correct 355 ms 177704 KB Output is correct
15 Correct 361 ms 177688 KB Output is correct
16 Correct 347 ms 177088 KB Output is correct
17 Correct 341 ms 177424 KB Output is correct
18 Correct 373 ms 177132 KB Output is correct
19 Correct 357 ms 177648 KB Output is correct
20 Correct 21 ms 4800 KB Output is correct
21 Correct 19 ms 4944 KB Output is correct
22 Correct 17 ms 5808 KB Output is correct
23 Correct 19 ms 4936 KB Output is correct
24 Correct 20 ms 4924 KB Output is correct
25 Correct 16 ms 4188 KB Output is correct
26 Correct 15 ms 4180 KB Output is correct
27 Correct 15 ms 4272 KB Output is correct
28 Correct 16 ms 4444 KB Output is correct
29 Incorrect 36 ms 7472 KB Output isn't correct
30 Halted 0 ms 0 KB -