Submission #746547

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
746547	2023-05-22 17:47:36	cscandkswon	Split the sequence (APIO14_sequence)	C++17	89 / 100	1291 ms	83812 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
using namespace std;
int N, K, v, w;
int A[100005];
long long S[100005];
long long D[100005][2];
int O[100005][205];
void dnc(int l, int r, int x, int y, int k) {
    if (l > r) return;
    int m = (l + r) >> 1;
    int i, p;
    long long q = 0;
    for (i = max(k - 1, x); i <= min(y, m - 1); i++) {
        if (q < (S[m] - S[i]) * (S[N] - S[m]) + D[i][w]) {
            q = (S[m] - S[i]) * (S[N] - S[m]) + D[i][w];
            p = i;
        }
    }
    D[m][v] = q;
    O[m][k] = p;
    if (l == r) return;
    dnc(l, m - 1, x, p, k);
    dnc(m + 1, r, p, y, k);
}
void backtrack(int x, int k) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:15: warning: unused variable 'c' [-Wunused-variable]
   37 |     int i, j, c = 0;
      |               ^
sequence.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:39:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     for (i = 1; i <= N; i++) scanf("%d", A + i);
      |                              ~~~~~^~~~~~~~~~~~~
sequence.cpp: In function 'void dnc(int, int, int, int, int)':
sequence.cpp:26:8: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |     dnc(l, m - 1, x, p, k);
      |     ~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29