Submission #473229

#	Time	Username	Problem	Language	Result	Execution time	Memory
473229		Lam_lai_cuoc_doi	Bigger segments (IZhO19_segments)	C++17	37 / 100	337 ms	138104 KiB

segments

#define task "AWARDS"

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 5e3 + 5;
constexpr int Inf = 1e9 + 7;

template<class T>
void read(T &x){
    x = 0;
    register int c;
    while((c = getchar()) && (c > '9'|| c < '0'));
    for(;c >='0' && c <='9';c = getchar())
      x = x * 10 + c - '0';
}


int n, dp[N][N];
ll a[N];

void Read()
{
    //cin >> n;
    read(n);
    for (int i = 1; i <= n; ++i)
        //cin >> a[i];
        read(a[i]);
    //reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] += a[i - 1];
}

void Sub_1()
{
    int ans(1);
    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = 1;
        for (int j = 1; j < i; ++j)
        {
            dp[i][j] = -Inf;
            for (int t = j - 1; ~t; --t)
                if (a[i] - a[j] >= a[j] - a[t])
                    dp[i][j] = max(dp[i][j], dp[j][t] + 1);
                else
                    break;
            if (i == n)
                ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;
}

void Sub_2()
{
    int ans(1);
    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = 1;
        dp[i][i] = -Inf;
        for (int j = i - 1, t = i - 2; j; --j)
        {
            if (t >= j)
                --t;
            while (~t && a[i] - a[j] >= a[j] - a[t])
                --t;

            dp[i][j] = -Inf;
            dp[i][j] = max(dp[i][j], dp[j][t + 1] + 1);
            dp[i][j] = max(dp[i][j], dp[i][j + 1]);
        }
        dp[i][0] = max(dp[i][1], dp[i][0]);
        if (i == n)
            ans = max(ans, dp[i][0]);
    }
    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    if (n <= 200)
        Sub_1();
    else
        Sub_2();
}

Compilation message (stderr)

segments.cpp: In function 'void read(T&)':
segments.cpp:18:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   18 |     register int c;
      |                  ^
segments.cpp: In instantiation of 'void read(T&) [with T = int]':
segments.cpp:31:11:   required from here
segments.cpp:18:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
segments.cpp: In instantiation of 'void read(T&) [with T = long long int]':
segments.cpp:34:18:   required from here
segments.cpp:18:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
segments.cpp: In function 'int32_t main()':
segments.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27