oj.uz

Submission #584269

# Submission time Handle Problem Language Result Execution time Memory
584269 2022-06-27T06:46:04 Z Arnch Election (BOI18_election) C++17
0 / 100
 3000 ms 312 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;


int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	string s; cin >>s;

	int q; cin >>q;
	while(q--) {
		int l, r; cin >>l >>r; l--, r--;
		string t = "", z = "";
		for(int i = l; i <= r; i++) t.push_back(s[i]);
		z = t;
		int sum = 0, cnt = 1e9;
		for(int j = 0; j <= Sz(z); j++) {
			for(int k = 0; k <= Sz(z) - j; k++) {
				t = z;
				int val = 0;
				sum = 0;
				for(int i = 0; i < j; i++) if(t[i] == 'T') t[i] = '?', val++;
				for(int i = Sz(t) - 1; i >= Sz(t) - k; i--) if(t[i] == 'T') t[i] = '?', val++;
				bool flag = true;
				for(int i = 0; i < Sz(t); i++) {
					if(t[i] == 'T') sum--;
					else if(t[i] == 'C') sum++;
					if(sum < 0) {
						flag = false;
						break;
					}
				}
				sum = 0;
				for(int i = Sz(t) - 1; i >= 0; i--) {
					if(t[i] == 'T') sum--;
					else if(t[i] == 'C') sum++;
					if(sum < 0) {
						flag = false;
						break;
					}
				}
				if(flag) {
					cnt = min(cnt, val);
				}
			}
		}
		cout<<cnt <<endl;
	}

    return 0;
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 312 KB Time limit exceeded
2 Halted 0 ms 0 KB -