oj.uz

Submission #985474

# Submission time Handle Problem Language Result Execution time Memory
985474 2024-05-17T23:36:56 Z Math4Life2020 Split the sequence (APIO14_sequence) C++17
0 / 100
 16 ms 3928 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

void solve(long long N, long long K, vector<long long> a, vector<long long> a0) {
	long long tval = 0;
	for (long long i=0;i<N;i++) {
		tval += a[i];
	}
	tval = tval*tval;
	deque<long long> d[K+1];
	long long dsums[K+1];
	for (long long i=0;i<=K;i++) {
		dsums[i]=0;
	}
	for (long long i=0;i<N;i++) {
		d[0].push_back(a[i]);
		dsums[0] += a[i];
	}
	for (long long t=0;t<(2*N);t++) {
		for (long long i=0;i<K;i++) {
			while (1) {
				long long r = d[i].back();
				if (max(dsums[i]-r,dsums[i+1]+r)<max(dsums[i],dsums[i+1])) {
					d[i].pop_back();
					d[i+1].push_front(r);
					dsums[i]=dsums[i]-r;
					dsums[i+1]=dsums[i+1]+r;
				} else {
					break;
				}
			}
		}
	}
	for (long long i=0;i<=K;i++) {
		tval -= dsums[i]*dsums[i];
		/*cout << "i="<<i<<", dsums="<<dsums[i]<<"\n";
		for (long long x: d[i]) {
			cout << "term: "<<x<<"\n";
		}*/
	}
	tval = tval/2;
	cout << tval <<"\n";
	string ans;
	int rtot = 0;
	for (int q=0;q<K;q++) {
		int count = 0;
		while (count<(d[q].size())) {
			if (a0[rtot] != 0) {
				count++;
			}
			rtot++;
		}
		ans += to_string(rtot);
		if (q != (K-1)) {
			ans += " ";
		}
	}
	cout << ans;
}

int main() {
	long long N,K; cin >> N >> K;
	vector<long long> a;
	vector<long long> a0;
	for (long long i=0;i<N;i++) {
		long long x; cin >> x;
		a0.push_back(x);
		if (x != 0) {
			a.push_back(x);
		}
	}
	K = min(K,(long long) (a.size()-1));
	solve(a.size(),K,a,a0);
}

Compilation message

sequence.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>, std::vector<long long int>)':
sequence.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (count<(d[q].size())) {
      |          ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 348 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Integer 200 violates the range [1, 199]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Integer 1000 violates the range [1, 999]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB contestant didn't find the optimal answer: 1695400000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3928 KB contestant didn't find the optimal answer: 19795776955 < 19795776960
2 Halted 0 ms 0 KB -