Submission #1832510
Source Code Expand
#include <bits/stdc++.h>
#define long long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define debug(X) cerr<< #X << " = " <<X << endl
#define debug2(X,Y) cerr<< #X << " = " <<X << ","<<#Y<<" = "<<Y<<endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;
inline void read(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for (;((c<48 || c>57) && c != '-') ;c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
inline void writeln(int x){
char buffor[21];
register int i=0;
int neg=0; if (x<0) {neg=1; x= -x;}
do{
buffor[i++]=(x%10)+'0';
x/=10;
} while(x);
i--;
if (neg) pc('-');
while(i>=0) pc(buffor[i--]);
pc('\n');
}
const int N= 1e5+10;
int n,k;
long p[N], a[N],s[N];
void input()
{
cin>>n>>k;
up(i,1,n) cin>>a[i], a[i]+= a[i-1];
}
void solve()
{
up(i,1,n)
if (a[i]- a[i-1]>0) p[i]+= a[i]- a[i-1];
up(i,1,n) p[i]+= p[i-1];
down(i,n,1)
if (a[i]- a[i-1]>0) s[i]+= a[i]- a[i-1];
down(i,n,1) s[i]+= s[i+1];
long res= -1e15;
up(i,1,n-k+1) res= max(res, p[i-1]+ s[i+k]+ max(0LL, a[i+k-1]- a[i-1]) );
cout<<res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);// don't use when interactive
#ifdef I_Love_Pork
#define TASK "tmp"
freopen(TASK".inp","r",stdin);
freopen(TASK".out","w",stdout);
#endif
input();
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Contiguous Repainting |
User |
I_Love_Pork |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1898 Byte |
Status |
AC |
Exec Time |
14 ms |
Memory |
2560 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
0_03.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
1 ms |
256 KB |
1_03.txt |
AC |
9 ms |
2560 KB |
1_04.txt |
AC |
13 ms |
2560 KB |
1_05.txt |
AC |
13 ms |
2560 KB |
1_06.txt |
AC |
13 ms |
2560 KB |
1_07.txt |
AC |
14 ms |
2560 KB |
1_08.txt |
AC |
13 ms |
2560 KB |
1_09.txt |
AC |
14 ms |
2560 KB |
1_10.txt |
AC |
13 ms |
2560 KB |
1_11.txt |
AC |
14 ms |
2560 KB |
1_12.txt |
AC |
13 ms |
2560 KB |
1_13.txt |
AC |
13 ms |
2560 KB |
1_14.txt |
AC |
13 ms |
2560 KB |
1_15.txt |
AC |
13 ms |
2560 KB |
1_16.txt |
AC |
14 ms |
2560 KB |
1_17.txt |
AC |
13 ms |
2560 KB |
1_18.txt |
AC |
14 ms |
2560 KB |
1_19.txt |
AC |
12 ms |
2560 KB |
1_20.txt |
AC |
14 ms |
2560 KB |
1_21.txt |
AC |
14 ms |
2560 KB |