# CFR 67 A. Partial Teacher ( DP, Greedy )

Problem - A - Codeforces
WA 好多次...

The first line of input contains the number of students n (2 ≤ n ≤ 1000). The second line gives (n - 1) characters consisting of "L", "R" and "=". For each pair of adjacent students "L" means that the left student has higher marks, "R" means that the right student has higher marks and "=" means that both have equal marks.
TL: 1000 ms
ML: 256 MB

O( N^2 )

9 RRRRRRLL : 1 2 3 4 5 6 7 2 1
5 LLLL : 5 4 3 2 1

```int N;
string cmp;

void init(){
cin >> N;
cin >> cmp;
}

vi ans;

void preprocess(){
ans = vi( N );
ans[ 0 ] = 1;
for( int i = 0; i < N - 1; ++i ){
if( cmp[ i ] == '=' ){
ans[ i + 1 ] = ans[ i ];
} else if( cmp[ i ] == 'L' ){
ans[ i + 1 ] = 1;
if( ans[ i ] == 1 ){
for( int j = i; j >= 0; --j ){
++ans[ j ];
if( j - 1 < 0 or cmp[ j - 1 ] == 'R' ){
break;
}
if( cmp[ j - 1 ] == 'L' and ans[ j - 1 ] > ans[ j ] ){
break;
}
}
}
} else{
ans[ i + 1 ] = ans[ i ] + 1;
}
}
}

void solve(){
for( int i = 0; i < N; ++i ){
cout << ans[ i ] << " \n"[ i + 1 == N ];
}
}
```