Submission #164085

#	Time	Username	Problem	Language	Result	Execution time	Memory
164085		dandrozavr	Bigger segments (IZhO19_segments)	C++14	37 / 100	1174 ms	146152 KiB

segments

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /🔥/   /▐/   /▌/ /▀/ /░/ /◐ / choose  your  own style

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/



//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>

using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>'
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;

#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair < ll , int >
#define pipii pair< int, pair < int , int > >
#define siz(n) (int)(n.size())
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int inf=1e9 + 7;
const ll inf18=1e18 + 7;
const int N=1e6 + 7;
const int MN = 2097152;
const int M = 1e9 + 7;

ll dp[3001][3001];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    #ifdef Estb_probitie
        freopen("input.txt", "r", stdin);
        freopen("output1.txt", "w", stdout);
    #endif

    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    ll pref[n];
    pref[0] = a[0];
    for (int i = 1; i < n; ++i)
        pref[i] = pref[i - 1] + a[i];

    for (int i = 0; i < n; ++i)
        fill(dp[i], dp[i] + n + 1, 1e17);


    dp[0][1] = a[0];
    ll nac[n + 2] = {};
    fill(nac, nac + n + 1, 1e9);
    nac[1] = 0;

    for (int i = 1; i < n; ++i)
    {
        bool byl = 1;

        for (int j = 1; j <= i + 1; ++j)
        {
            dp[i][j] = min(dp[i][j], a[i] + dp[i - 1][j]);

            if (nac[j - 1] == 1e9) continue;
            int l = nac[j - 1], r = i - 1;
            while(l < r)
            {
                int mid = ((l + r) >> 1) + 1;
                if (pref[i] - pref[mid] >= dp[mid][j - 1])
                    l = mid; else
                    r = mid - 1;
            }
            for (int l2 = max(0, l - 50); l2 <= min(i - 1, l + 50); ++l2)
            if (pref[i] - pref[l2] >= dp[l2][j - 1])
            {
                dp[i][j] = min(dp[i][j], pref[i] - pref[l2]);
                nac[j] = min(nac[j], 1ll * i);
////                cout<<i<<" "<<j<<" "<<l<<endl;
            }
        }
    }

    int ans = 0;
    for (int j = 1; j <= n; ++j)
        if (dp[n - 1][j] < 1e16)
        {
            ans = j;
        }
    cout << ans;

}

Compilation message (stderr)

segments.cpp:35:50: warning: missing terminating ' character
 #include <ext/pb_ds/detail/standard_policies.hpp>'
                                                  ^
segments.cpp:35:50: warning: extra tokens at end of #include directive
segments.cpp: In function 'int main()':
segments.cpp:91:14: warning: unused variable 'byl' [-Wunused-variable]
         bool byl = 1;
              ^~~

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