AOJ0603 Illumination

Illumination | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

まんまこれだ

Problem - C - Codeforces

Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad-'1' for a correctly identified cow and '0' otherwise.

と思ったけど，連続，非連続で違った．
連続して，またはの列に分ける．つの列を反転するとその前後の列を含む列になる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;

  vector<int> v(n);
  rep(i, n) cin >> v[i];

  vector<int> t;
  t.push_back(0);
  REP(i, 1, n) {
      if(v[i-1] == v[i]) {
          t.push_back(i);
      }
  }
  t.push_back(n);

  int ans = 0;
  rep(i, t.size()-1) {
      ans = max(ans, t[i+1] - t[i]);
  }

  rep(i, n) {
      int j = upper_bound(t.begin(), t.end(), i) - t.begin();
      int res = t[j+1] - t[j-2];
      ans = max(ans, res);
  }

  cout << ans << endl;

  return 0;
}
Mar 12th, 2016
aoj