Codeforces Round #386 (Div. 2), problem: (G) New Roads Solution in C/C++

By |2017-04-07T22:11:46+00:00January 6th, 2017|Categories: C/C++, Programming|Tags: , , , , , , , |

Codeforces Round #386 (Div. 2), problem: (G) New Roads Solution in C/C++ #include<stdio.h> #include<stdlib.h> typedef unsigned u; u D[222222],H[222222],P[222222],A[222222]; int main() { u n,d,x,i=-1,j,k,mi=0,ma=1; for(scanf("%u%u%u",&n,&d,&x);++i<d;)scanf("%u",D+i); for(i=d;i--;ma+=D[i]-1)if(D[i]>D[i+1])mi+=D[i]-D[i+1]; if(x<mi||x>ma){printf("-1\n");return 0;} for(A[i=0]=2;i++<d;)A[i]=A[i-1]+D[i-1]; for(i=1;++i<A[1];)P[i]=1; for(i=0;++i<d;) { k=D[i-1]-1; if(k>D[i]-1)k=D[i]-1; j=ma-x; if(j>k)j=k; ma-=j; j=A[i]-1-j; for(k=A[i]-1;++k<A[i+1];) { P[k]=j; if(j+1<A[i])++j; } } [...]