답안 #1028667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028667	2024-07-20T06:51:52 Z	Fatonim	Bigger segments (IZhO19_segments)	C++17	27 / 100	1500 ms	71004 KB

segments

// "We create our own demons"
#include <bits/stdc++.h>

using namespace std;

#ifdef ONPC
    #include "debug.h"
#else
    #define dbg(...)
#endif

#define int long long
#define ll long long
#define ld long double
#define pi pair<int, int>
// vector
#define sz(a) (int)((a).size())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxpos(x) (max_element(all(x)) - x.begin())
#define minpos(x) (min_element(all(x)) - x.begin())
#define rev(x) (reverse(all(x)))
// bits
#define popcount(n) __builtin_popcountll(n)
#define clz(n) __builtin_clzll(n)
// math
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
// ostream
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_queue = priority_queue<T, vector<T>, less<T>>;

template <class T> using V = vector<T>;
using vi = V<int>;
using vd = V<ld>;
using vb = V<bool>;
using vpi = V<pi>;
using vvi = V<vi>;
using vvb = V<vb>;

const int mod = 1e9 + 7; // 998244353 1e9 + 7
const ll inf = (int)(1e18) + 7;
const int inf_s = 1e9 + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 3000 + 3;
const int logn = 20;
const int maxn = 5e5 + 7;
/////////////////////////solve/////////////////////////

int a[maxn], p[maxn];
int dp[N][N];

void solve() {
    int n;
    cin >> n;

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

    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] + a[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = -inf;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            // dp[i][j] = dp[i - j][k]
            int sum = p[i] - p[i - j];
            for (int k = 1; k <= i - j; ++k) {
                int cur = p[i - j] - p[i - j - k];
                dbg(cur, sum);
                if (cur > sum) continue;
                chmax(dp[i][j], dp[i - j][k] + 1);
            }
            dbg(i, j, dp[i][j]);
        }
        dp[i][i] = 1;
    }

    int ans = 0;
    for (int j = 1; j <= n; ++j) {
        chmax(ans, dp[n][j]);
    }

    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
#ifdef ONPC
        cerr << "===========" << i << "===========" << '\n';
#endif
        solve();
    }

#ifdef ONPC
    cerr << endl << "Time " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Subtask #1
13.0 / 13.0

#	결과	메모리	Grader output
1	Correct	600 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	23 ms	4464 KB	Output is correct
17	Correct	44 ms	4444 KB	Output is correct
18	Correct	24 ms	4440 KB	Output is correct
19	Correct	22 ms	4440 KB	Output is correct
20	Correct	21 ms	4444 KB	Output is correct
21	Correct	24 ms	4444 KB	Output is correct
22	Correct	13 ms	3164 KB	Output is correct
23	Correct	6 ms	2392 KB	Output is correct
24	Correct	24 ms	4444 KB	Output is correct
25	Correct	24 ms	4440 KB	Output is correct
26	Correct	21 ms	4444 KB	Output is correct
27	Correct	20 ms	4444 KB	Output is correct
28	Correct	21 ms	4444 KB	Output is correct
29	Correct	32 ms	4696 KB	Output is correct
30	Correct	21 ms	4464 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	23 ms	4464 KB	Output is correct
17	Correct	44 ms	4444 KB	Output is correct
18	Correct	24 ms	4440 KB	Output is correct
19	Correct	22 ms	4440 KB	Output is correct
20	Correct	21 ms	4444 KB	Output is correct
21	Correct	24 ms	4444 KB	Output is correct
22	Correct	13 ms	3164 KB	Output is correct
23	Correct	6 ms	2392 KB	Output is correct
24	Correct	24 ms	4444 KB	Output is correct
25	Correct	24 ms	4440 KB	Output is correct
26	Correct	21 ms	4444 KB	Output is correct
27	Correct	20 ms	4444 KB	Output is correct
28	Correct	21 ms	4444 KB	Output is correct
29	Correct	32 ms	4696 KB	Output is correct
30	Correct	21 ms	4464 KB	Output is correct
31	Execution timed out	1567 ms	71004 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #4
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	23 ms	4464 KB	Output is correct
17	Correct	44 ms	4444 KB	Output is correct
18	Correct	24 ms	4440 KB	Output is correct
19	Correct	22 ms	4440 KB	Output is correct
20	Correct	21 ms	4444 KB	Output is correct
21	Correct	24 ms	4444 KB	Output is correct
22	Correct	13 ms	3164 KB	Output is correct
23	Correct	6 ms	2392 KB	Output is correct
24	Correct	24 ms	4444 KB	Output is correct
25	Correct	24 ms	4440 KB	Output is correct
26	Correct	21 ms	4444 KB	Output is correct
27	Correct	20 ms	4444 KB	Output is correct
28	Correct	21 ms	4444 KB	Output is correct
29	Correct	32 ms	4696 KB	Output is correct
30	Correct	21 ms	4464 KB	Output is correct
31	Execution timed out	1567 ms	71004 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	23 ms	4464 KB	Output is correct
17	Correct	44 ms	4444 KB	Output is correct
18	Correct	24 ms	4440 KB	Output is correct
19	Correct	22 ms	4440 KB	Output is correct
20	Correct	21 ms	4444 KB	Output is correct
21	Correct	24 ms	4444 KB	Output is correct
22	Correct	13 ms	3164 KB	Output is correct
23	Correct	6 ms	2392 KB	Output is correct
24	Correct	24 ms	4444 KB	Output is correct
25	Correct	24 ms	4440 KB	Output is correct
26	Correct	21 ms	4444 KB	Output is correct
27	Correct	20 ms	4444 KB	Output is correct
28	Correct	21 ms	4444 KB	Output is correct
29	Correct	32 ms	4696 KB	Output is correct
30	Correct	21 ms	4464 KB	Output is correct
31	Execution timed out	1567 ms	71004 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #1028667

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 14.0 / 14.0

Subtask #3 0 / 10.0

Subtask #4 0 / 36.0

Subtask #5 0 / 27.0

Subtask #1
13.0 / 13.0

Subtask #2
14.0 / 14.0

Subtask #3
0 / 10.0

Subtask #4
0 / 36.0

Subtask #5
0 / 27.0