Submission #800610

#	Time	Username	Problem	Language	Result	Execution time	Memory
800610		Dan4Life	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	195 ms	868 KiB

monochrome

#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]; if(n>2000) {cout<<0;return 0;}
    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;
}

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