CSES - APIO 2007

Submission details
Task:	Backup
Sender:	ArktinenKarpalo
Submission time:	2019-03-07 16:44:28 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	WRONG ANSWER	0.02 s	1, 2, 3	details
#3	TIME LIMIT EXCEEDED	--	3	details
#4	TIME LIMIT EXCEEDED	--	3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	TIME LIMIT EXCEEDED	--	2, 3	details
#7	ACCEPTED	0.02 s	1, 2, 3	details
#8	WRONG ANSWER	0.02 s	1, 2, 3	details
#9	TIME LIMIT EXCEEDED	--	2, 3	details
#10	TIME LIMIT EXCEEDED	--	2, 3	details
#11	TIME LIMIT EXCEEDED	--	3	details
#12	TIME LIMIT EXCEEDED	--	3	details
#13	TIME LIMIT EXCEEDED	--	3	details
#14	ACCEPTED	0.02 s	1, 2, 3	details
#15	TIME LIMIT EXCEEDED	--	2, 3	details
#16	TIME LIMIT EXCEEDED	--	3	details
#17	TIME LIMIT EXCEEDED	--	3	details
#18	TIME LIMIT EXCEEDED	--	2, 3	details
#19	TIME LIMIT EXCEEDED	--	2, 3	details
#20	TIME LIMIT EXCEEDED	--	3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:70:8: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   z[b] = i;
   ~~~~~^~~
input/code.cpp:69:8: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   z[a] = i;
   ~~~~~^~~

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, k, s[101010], z[101010], ss[101010];
ll ans = 1e14;
map<int,int> mp;

void haku(int otettu, int nyk, ll sum) {
	if(otettu == k)
		ans=min(sum,ans);
	if(nyk >= n-1 || otettu == k)
		return;
	haku(otettu, nyk+1, sum);
	haku(otettu+1, nyk+2, sum+ss[nyk]);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int T = 1;
	for(int g=0; g<T; g++) {
	ans = 1e14;
	cin >> n >> k;
	for(int i=0; i<n; i++) {
		cin >> s[i];
		if(i)
			ss[i-1] = s[i]-s[i-1];
		z[i] = 0;
	}
	haku(0,0,0);
//	cout << ans << " ";
//	ans = 1e14;
	for(int i=1; i<=k; i++) {
		int mini = 1e9+1;
		int a, b, oik=0;
		for(int j=0; j<n-1; j++) {
			mp.clear();
			if(z[j])
				continue;
			oik = j+1;
			int mod = 0;
			while(z[oik]) {
				int luku = mp[z[oik]];
				if(luku) {
					mod += oik-luku+1;
				} else {
					mp[z[oik]] = oik;
				}
				oik++;
			}
			if(oik == n)
				continue;
			if(s[oik]-s[j]-mod < mini) {
				a = j;
				b = oik;
				mini = s[oik]-s[j];
			}
		}
		z[a] = i;
		z[b] = i;
	}
	ans = 0;
	int ed = -1;
	for(int i=0; i<n; i++) {
		if(z[i]) {
			if(ed == -1) {
			ed = i;
			} else {
				ans += s[i]-s[ed];
				ed = -1;
			}
		}
	}
//	haku(0,0,0);
	cout << ans<<"\n";
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 1 0 1000000000` view save

correct output
`1000000000` view save

user output
`1000000000` view save

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`17 8 101266 101394 101458 101490 ...` view save

correct output
`340` view save

user output
`425` view save

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 49000 29983 53806 76909 106815 ...` view save

correct output
`411321413` view save

user output
(empty)

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 30000 29983 53806 76909 106815 ...` view save

correct output
`100755932` view save

user output
(empty)

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 10 126229031 250138471 333910089 443521720 ...` view save

correct output
`537092323` view save

user output
`537092323` view save

Test 6

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`10000 4999 168328 266967 462469 639689 ...` view save

correct output
`492516409` view save

user output
(empty)

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10 4 165 375 439 456 ...` view save

correct output
`44` view save

user output
`44` view save

Test 8

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`20 9 4336 4500 4552 4702 ...` view save

correct output
`773` view save

user output
`776` view save

Test 9

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`2001 1000 1230 1440 1630 2230 ...` view save

correct output
`493503` view save

user output
(empty)

Test 10

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`10000 3000 245408 417449 650973 863296 ...` view save

correct output
`101056127` view save

user output
(empty)

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`50000 20000 37035 37042 37046 37052 ...` view save

correct output
`129968` view save

user output
(empty)

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`99999 48000 15929 43928 65765 86730 ...` view save

correct output
`375524431` view save

user output
(empty)

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 1000 536 9214 34619 53734 ...` view save

correct output
`75975` view save

user output
(empty)

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10 4 5851 5854 5856 5859 ...` view save

correct output
`2664` view save

user output
`2664` view save

Test 15

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`100 45 3712 13742 17394 19428 ...` view save

correct output
`140256` view save

user output
(empty)

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`20000 400 3174 3175 3176 3179 ...` view save

correct output
`803105` view save

user output
(empty)

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 49000 3605 14510 18001 20881 ...` view save

correct output
`162316123` view save

user output
(empty)

Test 18

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`100 50 0 1000000 1000002 1000005 ...` view save

correct output
`1002499` view save

user output
(empty)

Test 19

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`1000 500 0 1000000 1000002 1000005 ...` view save

correct output
`1249999` view save

user output
(empty)

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 49494 123 65659 98427 114811 ...` view save

correct output
`250954854` view save

user output
(empty)

APIO 2007

Backup

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Tasks

Submissions (ArktinenKarpalo)