oj.uz

Submission #997494

# Submission time Handle Problem Language Result Execution time Memory
997494 2024-06-12T11:44:08 Z vjudge1 Split the sequence (APIO14_sequence) C++17
0 / 100
 27 ms 13648 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=2e5+5;
int const mod=1e9+7;
int m, n;
vector<long long> dp_before, dp_cur;
vector<int> dp_pr;
vector<long long> dp[205];
vector<int> pr[N];
long long prefix[N];
vector<int> mv;
long long C(int i, int j){
	if(i==0)
		return prefix[j]*prefix[j];
	return (prefix[j]-prefix[i-1])*(prefix[j]-prefix[i-1]);
}

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    dp_pr[mid]= best.second;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

long long solve() {
    dp_before.assign(n,0);
    dp_cur.assign(n,0);
    dp_pr.assign(n,0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);
    dp[0]=dp_before;
    pr[0]=dp_pr;
    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        
        dp[i]=dp_cur;
        pr[i]=dp_pr;
        dp_before = dp_cur;
    }
    int t=pr[m-1][n-1];
    for(int i=m-2;i>=0;i--){
    	mv.push_back(pr[i][t]);
    	t=pr[i][t];
    }
    return dp_before[n - 1];
}

int main(){
	cin>>n>>m;
	m++;
	long long total=0;
	int arr[n];
	for (int i = 0; i < n; ++i){
		cin>>arr[i];
		total+=arr[i];
	}
	prefix[0]=arr[0];
	for (int i = 1; i < n; ++i)
		prefix[i]=prefix[i-1]+arr[i];
	total*=total;
	total-=solve();
	total/=2;
	cout<<total<<endl;
	reverse(mv.begin(), mv.end());
	for(auto i:mv)
		cout<<i+1<<' ';
	cout<<endl;
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB contestant found the optimal answer: 108 == 108
2 Incorrect 2 ms 6492 KB declared answer doesn't correspond to the split scheme: declared = 999, real = 783
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Integer 50 violates the range [1, 49]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB declared answer doesn't correspond to the split scheme: declared = 610590000, real = 507121050
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB declared answer doesn't correspond to the split scheme: declared = 21503404, real = 14766072
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7260 KB declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1396709524
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 13648 KB declared answer doesn't correspond to the split scheme: declared = 19795776960, real = 16496882861
2 Halted 0 ms 0 KB -