oj.uz

Submission #1014077

# Submission time Handle Problem Language Result Execution time Memory
1014077 2024-07-04T10:28:32 Z peacebringer1667 Split the sequence (APIO14_sequence) C++17
11 / 100
 21 ms 3164 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
using namespace std;
const int maxn = 53;

struct CTDL{
	int pos = 0,k1 = 0,k2 = 0;
};

ll dp[maxn][maxn][maxn],sum[maxn];
CTDL trace[maxn][maxn][maxn];
inline ll S(int l,int r){
	return sum[r] - sum[l - 1];
}
int a[maxn];

void getdp(int l,int r,int k){
	for (int i = l ; i < r ; i++)
	  for (int k1 = 0 ; k1 < k ; k1++)
	    for (int k2 = 0 ; k2 + k1 < k ; k2++){
	    	ll T = dp[l][r][k1 + k2 + 1];
	    	
	    	ll tmp = dp[l][i][k1] + dp[i + 1][r][k2] + S(l,i)*S(i + 1,r);
	    	if (T < tmp){
	    		dp[l][r][k1 + k2 + 1] = tmp;
	    		trace[l][r][k1 + k2 + 1] = {i,k1,k2};
			}
		}
}

void Trace_back(int l,int r,int k){
	if (!k) return;
	CTDL t = trace[l][r][k];
	
	cout << t.pos << " ";
	Trace_back(l,t.pos,t.k1);
	Trace_back(t.pos + 1,r,t.k2);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
   // freopen("sequence.in","r",stdin);
  //  freopen("sequence.out","w",stdout);
    
	int n,k;
	cin >> n >> k;
	
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	} 

	for (int len = 1 ; len <= n ; len++)
	  for (int i = 1 ; i <= n - len + 1 ; i++)
	     getdp(i,i + len - 1,k);
	
    cout << dp[1][n][k] << "\n"; 
    Trace_back(1,n,k);
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 464 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 348 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 1884 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 21 ms 2072 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 1884 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 2 ms 2004 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 3 ms 1884 KB contestant found the optimal answer: 933702 == 933702
7 Correct 6 ms 1884 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 3 ms 1884 KB contestant found the optimal answer: 687136 == 687136
9 Correct 2 ms 1884 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 3 ms 1884 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 3164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -