Submission #376307

#	Time	Username	Problem	Language	Result	Execution time	Memory
376307		Halogen	Bigger segments (IZhO19_segments)	C++14	0 / 100	142 ms	262144 KiB

segments

#include <bits/stdc++.h>

using namespace std;

int N;
long long presum[505];

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 = 0;
    if (x >= N) {
        if (presum[x] - presum[z - 1] >= 0) return ans = 0;
        else return - N - 10;
    }
    else if (presum[x] - presum[z - 1] < 0) return memo[x][y][z] = dp(x + 1, y, z);
    else return memo[x][y][z] = max(
        dp(x + 1, y, z),
        1 + dp(x + 1, x, z)
    );

}

main() {
    scanf("%d", &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; i++) presum[i] += presum[i - 1];

    printf("%d\n", dp(1, 0, 0));
}

Compilation message (stderr)

segments.cpp:26:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main() {
      |      ^
segments.cpp: In function 'int main()':
segments.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
segments.cpp:30:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     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