fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sc(a) scanf("%d", &a)
  6. #define sc2(a, b) scanf("%d%d", &a, &b)
  7. #define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
  8. #define scs(a) scanf("%s", a)
  9. #define pri(x) printf("%d\n", x)
  10. #define prie(x) printf("%d ", x)
  11. #define mp make_pair
  12. #define pb push_back
  13. #define BUFF ios::sync_with_stdio(false);
  14. #define db(x) cerr << #x << " == " << x << endl
  15. #define dbs(x) cerr << x << endl
  16. #define ler freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  17. #define imprime(x, Y)                              \
  18.   for (int X = 0; X < Y; X++) cerr << x[X] << " "; \
  19.   cerr << endl;
  20. typedef long long int ll;
  21. typedef long double ld;
  22. typedef pair<int, int> ii;
  23. typedef vector<int> vi;
  24. typedef vector<ii> vii;
  25. typedef vector<vi> vvi;
  26. typedef vector<vector<ii> > vvii;
  27. const int INF = 0x3f3f3f3f;
  28. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  29. const ld pi = acos(-1);
  30. const int MOD = 1e9 + 7;
  31.  
  32. int main() {
  33. 	int n, init = 0;
  34. 	cin >> n;
  35. 	int first0 = n, last0 = 0;
  36. 	vector<int> v(n,0);
  37. 	for(int i=0; i<n; i++){
  38. 		cin >> v[i];
  39. 		if(v[i]){
  40. 			v[i] = -1;
  41. 			init++;
  42. 		}
  43. 		else{
  44. 		  first0 = min(first0,i);
  45. 		  last0 = max(last0,i+1);
  46. 		  v[i] = 1; 
  47. 		}
  48. 	}
  49. 	int l = first0, r = first0+1, sum, max;
  50. 	if(first0<n){
  51. 		sum = v[first0];
  52. 		max = sum;
  53. 	}else{
  54. 		sum = 0;
  55. 		max = -1;
  56. 	}
  57. 	while(l<last0){
  58. 		//cout << l << ' '<< r << ' ' << sum << endl;
  59. 	    if((sum>0 || l==r-1) && r<last0) sum += v[r++];
  60. 		else if(sum==0 || r==last0) sum -= v[l++];
  61. 	    else if(r<last0) sum+=v[r++];
  62. 	    else sum-=v[l++];
  63. 	    if(sum>max) max = sum;
  64. 	}
  65. 	cout << init+max << endl;
  66.  	return 0;
  67. }
Success #stdin #stdout 0s 15224KB
comments (?)
stdin
copy 
11
0 0 1 1 1 1 1 1 0 0 0
stdout
copy 
9
https://ideone.com/d1dUNO
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!