제출 #1357423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357423		phtung	3단 점프 (JOI19_jumps)	C++20	19 / 100	1065 ms	201596 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long

const int inf = 1e18 + 7;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int n, q, a[maxn]; 

namespace subtask1
{
    void solve()
    {
        while(q--)
        {
            int l, r;
            cin >> l >> r; 

            int res = 0;
            for(int i = l; i <= r - 2; i++)
            {
                for(int j = i + 1; j <= r - 1; j++)
                {
                    if(j - i > r - j) break; 
                    for(int k = j + 1; k <= r; k++)
                    {
                        if(k - j < j - i) continue;
                        res = max(res, a[i] + a[j] + a[k]);
                    }
                }
            }
        
            cout << res << "\n";
        }
    }
}

namespace subtask2
{
    struct segTree
    {
        vector<int> st; 

        segTree(int n)
        {
            st.resize(4 * n + 5); 
        }

        void build(int id, int l, int r)
        {
            if(l == r)
            {
                st[id] = a[l];
                return; 
            }
            int mid = l + r >> 1;
            build(id * 2, l, mid);
            build(id * 2 + 1, mid + 1, r);
            st[id] = max(st[id * 2], st[id * 2 + 1]); 
        }

        int get(int id, int l, int r, int u, int v)
        {
            if(l > v || r < u) return -inf;
            if(l >= u && r <= v) return st[id]; 
            int mid = l + r >> 1;
            return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
        }
    };

    void solve()
    {   
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        segTree st(n);
        st.build(1, 1, n);

        for(int len = 3; len <= n; len++)
        {
            for(int i = 1; i <= n - len + 1; i++)
            {
                int j = i + len - 1;
                
                if(len == 3) dp[i][j] = a[i] + a[i + 1] + a[j]; 

                else 
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]); 
                    int v = st.get(1, 1, n, i + 1, (i + j) / 2);
                    dp[i][j] = max(dp[i][j], a[i] + a[j] + v);
                }
            }
        }

        while(q--)
        {
            int l, r;
            cin >> l >> r; 
            cout << dp[l][r] << "\n";
        }
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i]; 

    cin >> q; 

    if(n <= 100 && q <= 100)
    {
        subtask1::solve();
        return; 
    }

    if(n <= 5000)
    {
        subtask2::solve();
        return;
    }


}

signed main()
{
    if(fopen(name".INP","r"))
    {
        freopen(name".INP","r",stdin);
        // freopen(name".OUT","w",stdout);
    }


    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t start = clock();

    int t = 1;

    while(t--) solve();

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int main()':
jumps.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 5 / 5
• 서브태스크 2: 14 / 14
• 서브태스크 3: 0 / 27
• 서브태스크 4: 0 / 54