Submission #601267

#TimeUsernameProblemLanguageResultExecution timeMemory
601267jjianglySplit the sequence (APIO14_sequence)C++14
Compilation error
0 ms0 KiB
//#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define TASK "QNOI"
#define ll long long
#define f first
#define s second
#define pb push_back
#define For(i,l,r) for (int i=l;i<=r;i++)
#define Fod(i,r,l) for (int i=r;i>=l;i--)
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

typedef pair<int,int> ii;
typedef unsigned long long ull;
const int N = 1000;
const int oo = 1e9;
typedef int long long

ll dp[N + 5][N + 5];
signed main () {
	faster;
	#ifndef ONLINE_JUDGE
	freopen(TASK".inp", "r", stdin);
	freopen(TASK".out", "w", stdout);
	#endif

	int n, k;
	cin >> n >> k;

	vector <int> a(n + 1, 0);
	vector <int> pre(n + 1, 0);

	For(i, 1, n) cin >> a[i], pre[i] = pre[i - 1] + a[i];

	For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
	dp[0][0] = 0;

	For(i, 1, n)
		For(j, 1, k) {
			For(l, 0, i - 1)
				dp[i][j] = max(dp[i][j], dp[l][j - 1] + (pre[n] - pre[i]) * (pre[i] - pre[l]));
		}

	ll ans = 0;

	For(i, 1, n) ans = max(ans, dp[i][k]);

	cout << ans << endl;

	vector <int> res;

	int cnt = k - 1;

	int tmp = 1;

	For(i, 1, n) {
		if(dp[i][k] == ans) {
			res.pb(i);

			tmp = i;

			Fod(j, i - 1, 1) {
				if(cnt == 0) break;

				if(dp[j][cnt] + (pre[n] - pre[tmp]) * (pre[tmp] - pre[j]) == ans) {
					res.pb(j);
					cnt--;
					ans = dp[j][cnt + 1]; 
					tmp = j;
				}
			}
			break;
		}
	}

	reverse(res.begin(), res.end());
	for(int i : res) cout << i << " ";
}

Compilation message (stderr)

sequence.cpp:4:12: error: 'long long long' is too long for GCC
    4 | #define ll long long
      |            ^~~~
sequence.cpp:19:1: note: in expansion of macro 'll'
   19 | ll dp[N + 5][N + 5];
      | ^~
sequence.cpp:4:17: error: 'long long long' is too long for GCC
    4 | #define ll long long
      |                 ^~~~
sequence.cpp:19:1: note: in expansion of macro 'll'
   19 | ll dp[N + 5][N + 5];
      | ^~
sequence.cpp: In function 'int main()':
sequence.cpp:35:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |  For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
      |                              ^
sequence.cpp:35:30: error: structured binding declaration cannot have type 'dp' {aka 'long long int [1005][1005]'}
   35 |  For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
      |                              ^~~
sequence.cpp:35:30: note: type must be cv-qualified 'auto' or reference to cv-qualified 'auto'
sequence.cpp:35:31: error: redeclaration of 'auto j'
   35 |  For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
      |                               ^
sequence.cpp:35:19: note: 'int j' previously declared here
   35 |  For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
      |                   ^
sequence.cpp:8:29: note: in definition of macro 'For'
    8 | #define For(i,l,r) for (int i=l;i<=r;i++)
      |                             ^
sequence.cpp:35:33: error: expected initializer before '[' token
   35 |  For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
      |                                 ^
sequence.cpp:35:33: error: expected ';' before '[' token
sequence.cpp:36:5: error: expected identifier before numeric constant
   36 |  dp[0][0] = 0;
      |     ^
sequence.cpp:36:5: error: expected ']' before numeric constant
   36 |  dp[0][0] = 0;
      |     ^
      |     ]
sequence.cpp:36:4: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  dp[0][0] = 0;
      |    ^
sequence.cpp:36:4: error: structured binding declaration cannot have type 'dp' {aka 'long long int [1005][1005]'}
sequence.cpp:36:4: note: type must be cv-qualified 'auto' or reference to cv-qualified 'auto'
sequence.cpp:36:4: error: empty structured binding declaration
sequence.cpp:36:7: error: expected initializer before '[' token
   36 |  dp[0][0] = 0;
      |       ^
sequence.cpp:41:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     dp[i][j] = max(dp[i][j], dp[l][j - 1] + (pre[n] - pre[i]) * (pre[i] - pre[l]));
      |       ^
sequence.cpp:41:7: error: structured binding declaration cannot have type 'dp' {aka 'long long int [1005][1005]'}
   41 |     dp[i][j] = max(dp[i][j], dp[l][j - 1] + (pre[n] - pre[i]) * (pre[i] - pre[l]));
      |       ^~~
sequence.cpp:41:7: note: type must be cv-qualified 'auto' or reference to cv-qualified 'auto'
sequence.cpp:41:10: error: expected initializer before '[' token
   41 |     dp[i][j] = max(dp[i][j], dp[l][j - 1] + (pre[n] - pre[i]) * (pre[i] - pre[l]));
      |          ^
sequence.cpp:41:10: error: expected ';' before '[' token
sequence.cpp:46:32: error: expected primary-expression before '[' token
   46 |  For(i, 1, n) ans = max(ans, dp[i][k]);
      |                                ^
sequence.cpp:57:8: error: expected unqualified-id before '[' token
   57 |   if(dp[i][k] == ans) {
      |        ^
sequence.cpp:65:10: error: expected unqualified-id before '[' token
   65 |     if(dp[j][cnt] + (pre[n] - pre[tmp]) * (pre[tmp] - pre[j]) == ans) {
      |          ^
sequence.cpp:68:14: error: expected primary-expression before '[' token
   68 |      ans = dp[j][cnt + 1];
      |              ^
sequence.cpp:36:4: warning: unused structured binding declaration [-Wunused-variable]
   36 |  dp[0][0] = 0;
      |    ^
sequence.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen(TASK".inp", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen(TASK".out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~