Submission #376334

#	Time	Username	Problem	Language	Result	Execution time	Memory
376334		Halogen	Bigger segments (IZhO19_segments)	C++14	0 / 100	156 ms	262148 KiB

segments

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int N, presum[500005];
 
int memo[505][505][505];
 
int dp(int x, int y, int z) {
    if (memo[x][y][z] != -1) return memo[x][y][z];
    int ans;
    int preseg = presum[y] - presum[z], curseg = presum[x] - presum[y];

    if (x > N) {
        if (preseg > curseg) ans = -N - 5;
        else ans = 0;
    }

    else if (preseg > curseg) ans = dp(x + 1, y, z);

    else ans = max(
        dp(x + 1, y, z), 
        1 + dp(x + 1, x, y)
    );
 
    // printf("%lld %lld %lld %lld\n", ans, x, y, z);
    return ans;
}
 
main() {
    scanf("%lld", &N);
    memset(memo, -1, sizeof(memo));
    memset(presum, 0, sizeof(presum));
    for (int i = 1; i <= N; i++) scanf("%lld", &presum[i]);
    for (int i = 2; i <= N + 1; i++) presum[i] += presum[i - 1];
 
    printf("%lld\n", max(0ll, dp(1, 0, 0) + 1));
}

Compilation message (stderr)

segments.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main() {
      |      ^
segments.cpp: In function 'int main()':
segments.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
segments.cpp:36:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     for (int i = 1; i <= N; i++) scanf("%lld", &presum[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~

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