CSES - UKIEPC 2016

Submission details
Task:	Gondolas
Sender:	Game of Nolife
Submission time:	2016-11-12 13:41:46 +0200
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	ACCEPTED	0.06 s	details
#3	ACCEPTED	0.07 s	details
#4	ACCEPTED	0.06 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.29 s	details
#8	ACCEPTED	0.30 s	details
#9	ACCEPTED	0.22 s	details
#10	ACCEPTED	0.29 s	details
#11	ACCEPTED	0.20 s	details
#12	ACCEPTED	0.06 s	details
#13	ACCEPTED	0.07 s	details
#14	ACCEPTED	0.09 s	details
#15	ACCEPTED	0.15 s	details
#16	ACCEPTED	0.10 s	details
#17	ACCEPTED	0.06 s	details
#18	ACCEPTED	0.08 s	details
#19	ACCEPTED	0.06 s	details
#20	ACCEPTED	0.10 s	details
#21	ACCEPTED	0.10 s	details
#22	ACCEPTED	0.32 s	details
#23	ACCEPTED	0.06 s	details
#24	ACCEPTED	0.42 s	details
#25	ACCEPTED	0.39 s	details
#26	ACCEPTED	0.16 s	details
#27	ACCEPTED	0.50 s	details
#28	ACCEPTED	0.23 s	details
#29	ACCEPTED	0.41 s	details
#30	ACCEPTED	0.41 s	details
#31	ACCEPTED	0.53 s	details
#32	ACCEPTED	0.52 s	details
#33	ACCEPTED	0.06 s	details
#34	ACCEPTED	0.44 s	details
#35	ACCEPTED	0.42 s	details
#36	ACCEPTED	0.41 s	details
#37	ACCEPTED	0.43 s	details
#38	ACCEPTED	0.52 s	details
#39	ACCEPTED	0.52 s	details
#40	ACCEPTED	0.06 s	details
#41	ACCEPTED	0.06 s	details
#42	ACCEPTED	0.06 s	details
#43	ACCEPTED	0.05 s	details
#44	ACCEPTED	0.06 s	details

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int dp[444][444];
int f[444][444];
int n,t,g;

pair<int, vector<int> > solve(vector<int> xs){
	for (int i=0;i<=n+1;i++){
		for (int ii=0;ii<=g+1;ii++){
			dp[i][ii]=1e8;
		}
	}
	dp[0][0]=0;
	for (int i=0;i<n;i++){
		for (int ii=0;ii<g;ii++){
			int c=0;
			int su=0;
			for (int j=i;j<n;j++){
				c++;
				su+=xs[j];
				if (dp[i][ii]+xs[j]*c-su<dp[j+1][ii+1]){
					dp[j+1][ii+1]=dp[i][ii]+xs[j]*c-su;
					f[j+1][ii+1]=i;
				}
			}
		}
	}
	assert(dp[n][g]<1e8);
	int v=dp[n][g];
	vector<int> vv;
	int ti=n;
	for (int a=g;a>0;a--){
		vv.push_back(xs[ti-1]);
		ti=f[ti][a];
	}
	return {v, vv};
}

int solve2(vector<int> xs, int offs){
	vector<int> ys;
	for (int x:xs){
		ys.push_back((x-offs+8*t)%(2*t));
	}
	sort(ys.begin(), ys.end());
	auto v=solve(ys);
	return v.F;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>t>>g;
	g=min(g, n);
	vector<int> xs;
	for (int i=0;i<n;i++){
		int x;
		cin>>x;
		xs.push_back(x%(2*t));
	}
	sort(xs.begin(), xs.end());
	auto aa=solve(xs);
	int v=aa.F;
	sort(aa.S.begin(), aa.S.end());
	int mi=1e9;
	int mii=0;
	for (int i=0;i<(int)aa.S.size();i++){
		if (i+1==(int)aa.S.size()){
			if (aa.S[0]+t*2-aa.S[i]<mi){
				mi=aa.S[0]+t*2-aa.S[i];
				mii=i;
			}
		}
		else if (aa.S[i+1]-aa.S[i]<mi){
			mi=aa.S[i+1]-aa.S[i];
			mii=i;
		}
	}
	if (mii+1==(int)aa.S.size()){
		for (int j=aa.S.back();j<2*t;j++){
			v=min(v, solve2(xs, j));
			v=min(v, solve2(xs, -j));
		}
		for (int j=0;j<=aa.S[0];j++){
			v=min(v, solve2(xs, j));
			v=min(v, solve2(xs, -j));
		}
	}
	else{
		for (int j=aa.S[mii];j<=aa.S[mii+1];j++){
			v=min(v, solve2(xs, j));
			v=min(v, solve2(xs, -j));
		}
	}
	cout<<v<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`32 39 4 681306 435214 1554 470233 ...` view save

correct output
`183` view save

user output
`183` view save

Test 2

Verdict: ACCEPTED

input
`94 205 25 154150 167683 411531 64924 ...` view save

correct output
`328` view save

user output
`328` view save

Test 3

Verdict: ACCEPTED

input
`63 329 33 791965 121438 487872 197074 ...` view save

correct output
`133` view save

user output
`133` view save

Test 4

Verdict: ACCEPTED

input
`70 253 28 853321 662592 538431 311761 ...` view save

correct output
`203` view save

user output
`203` view save

Test 5

Verdict: ACCEPTED

input
`75 146 58 71431 174034 198572 717231 ...` view save

correct output
`6` view save

user output
`6` view save

Test 6

Verdict: ACCEPTED

input
`50 210 38 508372 208598 621692 276794 ...` view save

correct output
`11` view save

user output
`11` view save

Test 7

Verdict: ACCEPTED

input
`400 261 30 122770 252639 652115 865847 ...` view save

correct output
`2438` view save

user output
`2438` view save

Test 8

Verdict: ACCEPTED

input
`400 309 128 415910 619728 298494 977650 ...` view save

correct output
`333` view save

user output
`333` view save

Test 9

Verdict: ACCEPTED

input
`400 356 162 104184 601951 422624 370531 ...` view save

correct output
`265` view save

user output
`265` view save

Test 10

Verdict: ACCEPTED

input
`400 312 215 359148 808684 945274 604226 ...` view save

correct output
`76` view save

user output
`76` view save

Test 11

Verdict: ACCEPTED

input
`325 713 168 826229 196639 317967 8558 ...` view save

correct output
`294` view save

user output
`294` view save

Test 12

Verdict: ACCEPTED

input
`42 2 42 683073 532140 174856 51368 ...` view save

correct output
`0` view save

user output
`0` view save

Test 13

Verdict: ACCEPTED

input
`203 516 366 125553 642375 63137 608569 ...` view save

correct output
`0` view save

user output
`0` view save

Test 14

Verdict: ACCEPTED

input
`199 234 251 281253 491509 139389 436824 ...` view save

correct output
`0` view save

user output
`0` view save

Test 15

Verdict: ACCEPTED

input
`315 442 326 750778 381993 661296 156508 ...` view save

correct output
`0` view save

user output
`0` view save

Test 16

Verdict: ACCEPTED

input
`328 150 7 43275 248257 847043 99790 ...` view save

correct output
`5990` view save

user output
`5990` view save

Test 17

Verdict: ACCEPTED

input
`109 139 17 756544 653138 951489 311818 ...` view save

correct output
`519` view save

user output
`519` view save

Test 18

Verdict: ACCEPTED

input
`134 553 27 147387 129153 719770 427935 ...` view save

correct output
`1291` view save

user output
`1291` view save

Test 19

Verdict: ACCEPTED

input
`145 241 2 676743 605609 180247 181812 ...` view save

correct output
`16132` view save

user output
`16132` view save

Test 20

Verdict: ACCEPTED

input
`199 345 1 860055 518304 632757 227941 ...` view save

correct output
`63718` view save

user output
`63718` view save

Test 21

Verdict: ACCEPTED

input
`237 305 50 322166 709644 908880 898007 ...` view save

correct output
`732` view save

user output
`732` view save

Test 22

Verdict: ACCEPTED

input
`400 448 110 759554 617824 923199 28933 ...` view save

correct output
`682` view save

user output
`682` view save

Test 23

Verdict: ACCEPTED

input
`20 43 22 227704 798839 578770 318490 ...` view save

correct output
`0` view save

user output
`0` view save

Test 24

Verdict: ACCEPTED

input
`400 571 70 450921 468211 132387 47354 ...` view save

correct output
`1770` view save

user output
`1770` view save

Test 25

Verdict: ACCEPTED

input
`400 511 70 858453 872050 610960 953293 ...` view save

correct output
`1591` view save

user output
`1591` view save

Test 26

Verdict: ACCEPTED

input
`400 168 70 4459 674845 367823 294137 ...` view save

correct output
`490` view save

user output
`490` view save

Test 27

Verdict: ACCEPTED

input
`400 680 70 30654 191088 801200 207158 ...` view save

correct output
`2102` view save

user output
`2102` view save

Test 28

Verdict: ACCEPTED

input
`400 248 9 470894 893438 325348 641558 ...` view save

correct output
`9158` view save

user output
`9158` view save

Test 29

Verdict: ACCEPTED

input
`400 382 9 199594 909749 628471 402271 ...` view save

correct output
`14426` view save

user output
`14426` view save

Test 30

Verdict: ACCEPTED

input
`400 428 9 482354 949600 607474 999204 ...` view save

correct output
`16028` view save

user output
`16028` view save

Test 31

Verdict: ACCEPTED

input
`400 720 29 188913 504810 623401 693477 ...` view save

correct output
`6872` view save

user output
`6872` view save

Test 32

Verdict: ACCEPTED

input
`400 720 29 665160 117237 952099 664974 ...` view save

correct output
`6875` view save

user output
`6875` view save

Test 33

Verdict: ACCEPTED

input
`17 15 34 930291 502763 967298 799893 ...` view save

correct output
`0` view save

user output
`0` view save

Test 34

Verdict: ACCEPTED

input
`400 720 255 248532 531967 568554 368539 ...` view save

correct output
`207` view save

user output
`207` view save

Test 35

Verdict: ACCEPTED

input
`400 720 383 587057 127300 561898 335689 ...` view save

correct output
`17` view save

user output
`17` view save

Test 36

Verdict: ACCEPTED

input
`400 720 127 587057 127300 561898 335689 ...` view save

correct output
`1007` view save

user output
`1007` view save

Test 37

Verdict: ACCEPTED

input
`400 720 399 554238 475586 539758 602129 ...` view save

correct output
`1` view save

user output
`1` view save

Test 38

Verdict: ACCEPTED

input
`400 720 67 498986 209095 87086 627358 ...` view save

correct output
`2576` view save

user output
`2576` view save

Test 39

Verdict: ACCEPTED

input
`400 720 25 52948 388352 380718 137663 ...` view save

correct output
`9211` view save

user output
`9211` view save

Test 40

Verdict: ACCEPTED

input
`13 34 8 663490 977749 760140 95431 ...` view save

correct output
`5` view save

user output
`5` view save

Test 41

Verdict: ACCEPTED

input
`12 20 3 193357 939494 993606 22131 ...` view save

correct output
`37` view save

user output
`37` view save

Test 42

Verdict: ACCEPTED

input
`58 281 30 980435 768397 647975 798884 ...` view save

correct output
`99` view save

user output
`99` view save

Test 43

Verdict: ACCEPTED

input
`96 72 69 567259 416559 401648 673446 ...` view save

correct output
`0` view save

user output
`0` view save

Test 44

Verdict: ACCEPTED

input
`96 249 90 666268 812077 949656 878404 ...` view save

correct output
`0` view save

user output
`0` view save

UKIEPC 2016

Gondolas

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

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Tasks

Submissions (Game of Nolife)