Submission #800608

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
800608	2023-08-01 16:43:19	Dan4Life	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	177 ms	5220 KiB

monochrome

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
#include <bits/stdc++.h>
using namespace std;
const int N = (int)4e3+10;
string s; int n, ans, tot, fen[N], st[N];
void upd(int x, int v){ for(; x<N; x+=x&-x) fen[x]+=v; }
int sum(int x){ int s=0; for(; x>0; x-=x&-x)s+=fen[x]; return s; }
int sum(int a, int b){ return (a<=b)*(sum(b)-sum(a-1)); }
int main()
{
    cin >> n >> s; vector<int> v[2];
    for(int i = 0; i < 2*n; i++) v[s[i]>'B'].push_back(i+1);
    for(int k = 0; k < n; k++){ tot=0;
        for(int i = 0; i < n; i++){
            int a = v[0][i], b = v[1][(i+k)%n];
            if(a>b) swap(a,b); st[a] = a; st[b]=a;
        }
        for(int i = 1; i <= 2*n; i++){
            if(st[i]==i) upd(st[i],1);
            else tot+=sum(st[i]+1,i), upd(st[i],-1);
        }
        ans = max(ans, tot);
    }
    cout << ans;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:16:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |             if(a>b) swap(a,b); st[a] = a; st[b]=a;
      |             ^~
monochrome.cpp:16:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |             if(a>b) swap(a,b); st[a] = a; st[b]=a;
      |                                ^~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65