Submission #657352

#	Time	Username	Problem	Language	Result	Execution time	Memory
657352		Juan	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	19 ms	4076 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, INF = 0x3f3f3f3f;

char v[maxn];
vector<int> vJ, vO, vI;
int cost[maxn][3];

int main(){
	int n, k; cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> v[i];
		if(v[i]=='J') vJ.push_back(i);
		if(v[i]=='O') vO.push_back(i);
		if(v[i]=='I') vI.push_back(i);
	}

	memset(cost, INF, sizeof cost);
	int beginO=INF, beginI=INF;
	for(int i = 0, cnt=0; i < n; i++){
		if(cnt < vJ.size() && i==vJ[cnt]) cnt++;
		if(cnt==k && beginO==INF) beginO = i+1;
		if(cnt>=k)
			cost[i+1][0] = i - vJ[cnt-k] - (k-1);
		else cost[i+1][0] = INF;
	}

	int invalidO=0;
	for(; invalidO < vO.size(); invalidO++) if(vO[invalidO]>=beginO) break;
	for(int i = beginO, cnt=0; i < n; i++){
		if(cnt+invalidO < vO.size() && i==vO[cnt+invalidO]) cnt++;
		if(cnt==k && beginI==INF) beginI = i+1;
		if(cnt>=k)
			cost[i+1][1] = cost[vO[cnt-k+invalidO]][0] + i - vO[cnt-k+invalidO] - (k-1);
		else cost[i+1][1] = INF;
	}

	int invalidI=0;
	for(; invalidI < vI.size(); invalidI++) if(vI[invalidI]>=beginI) break;
	for(int i = beginI, cnt=0; i < n; i++){
		if(cnt+invalidI < vI.size() && i==vI[cnt+invalidI]) cnt++;
		if(cnt>=k)
			cost[i+1][2] = cost[vI[cnt-k+invalidI]][1] + i - vI[cnt-k+invalidI] - (k-1);
		else cost[i+1][2] = INF;
	}

	int ans = INF;
	for(int i = beginI; i <= n; i++) ans = min(ans, cost[i][2]);
	cout << (ans==INF ? -1 : ans) << '\n';
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:21:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if(cnt < vJ.size() && i==vJ[cnt]) cnt++;
      |      ~~~~^~~~~~~~~~~
ho_t2.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(; invalidO < vO.size(); invalidO++) if(vO[invalidO]>=beginO) break;
      |        ~~~~~~~~~^~~~~~~~~~~
ho_t2.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   if(cnt+invalidO < vO.size() && i==vO[cnt+invalidO]) cnt++;
      |      ~~~~~~~~~~~~~^~~~~~~~~~~
ho_t2.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(; invalidI < vI.size(); invalidI++) if(vI[invalidI]>=beginI) break;
      |        ~~~~~~~~~^~~~~~~~~~~
ho_t2.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   if(cnt+invalidI < vI.size() && i==vI[cnt+invalidI]) cnt++;
      |      ~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87