Codeforces Gym 100513G G. FacePalm Accounting

G. FacePalm Accounting

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/gym/100513/problem/G

Description

An owner of a small company FacePalm has recently learned that the city authorities plan to offer to small businesses to participate in improving parks and garden squares. However, credible sources informed the FacePalm owner that the loss-making companies will not get such an offer. Moreover, the sources have also told how loss-making companies will be determined.

A company will be considered loss-making if for every k contiguous days the total income of the company is negative.

The FacePalm owner discussed the situation with his chief accountant, and they decided to change the report so that the company would look loss-making.

The company report for n days can be represented as a sequence of integers a1, a2, ..., an, where ai is the company income in the dayi (negative values correspond to losses).

The accountant can change any values in this sequence, but no updated value can become less than the smallest value in the original report — otherwise the updated report will look absolutely implausible. Besides, the accountant wants the total change of the values to be as small as possible.

We will assume that the total change of the values is $\text{[math]}$ , where $\text{[math]}$ is the i-th value in the updated report.

Your task is to calculate the minimum required total change of the values and provide the updated report.

Input

The first line contains integers n and k (1 ≤ k ≤ n ≤ 2·105) — the number of days in the report and the number of days in the definition of loss-making company.

The second line contains n space-separated integers a1, a2, ..., an ( - 10000 ≤ ai ≤ 10000), where ai is the company income in dayi.

It is guaranteed that at least one value of ai is negative.

Output

In the first line print the required minimum total change. In the second line print the corresponding updated report. No value in the updated report can be less than the minimum value of the original report.

If there are multiple solutions, print any of them.

Sample Input

5 4
3 -3 -1 1 2

Sample Output

1
2 -3 -1 1 2

HINT

题意

对此序列任意的K长度区间，需满足sum（k）小于0，问你最小修改差是多少，且修改的值不得小于原序列中最小值，

题解：

贪心，每次从K区间中右到左来修改

代码

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <ctime>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <set>
 8 #include <vector>
 9 #include <queue>
10 #include <map>
11 #include <stack>
12 #define inf 1000000007
13 #define mod 1000000007
14 using namespace std;
15 typedef __int64 ll;
16 inline ll read()
17 {
18     ll x=0,f=1;
19     char ch=getchar();
20     while(ch<'0'||ch>'9')
21     {
22         if(ch=='-')f=-1;
23         ch=getchar();
24     }
25     while(ch>='0'&&ch<='9')
26     {
27         x=x*10+ch-'0';
28         ch=getchar();
29     }
30     return x*f;
31 }
32 //*******************************************************************
33 ll a[200005];
34 
35 int main()
36 {
37     ll n,k;
38    ll minn=inf;
39 
40     scanf("%I64d%I64d",&n,&k);
41     for(int i=1; i<=n; i++)
42         scanf("%I64d",&a[i]),minn=min(minn,a[i]);
43     ll sum=0;
44 
45     for(int i=1; i<k; i++)
46     {
47         sum+=a[i];
48     }
49     ll ans=0;
50     for(int i=k; i<=n; i++)
51     {
52         sum+=(a[i]-a[i-k]);
53         if(sum>=0)
54         {
55             ll tmp=sum+1; //printf("1111");
56             ans+=sum+1;
57             int j=i;
58             while(tmp>0)
59             {
60 
61 
62                ll  gg=min(a[j]-minn,tmp);
63                 a[j]-=gg;
64                 tmp-=gg;
65                 j--;
66             }
67             sum=-1;
68         }
69     }
70     printf("%I64d
",ans);
71     for(int i=1; i<=n; i++)
72     {
73         printf("%I64d ",a[i]);
74     }
75     return 0;
76 }

View Code