Submission #854247

#TimeUsernameProblemLanguageResultExecution timeMemory
854247LeVanThucJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
9 ms8540 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> template<class T1,class T2> bool maximize(T1 &x,const T2 &y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,const T2 &y) { if(x>y) { x=y; return 1; } return 0; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.INP","r",stdin); freopen("output.OUT","w",stdout); #endif } const ll N=2e5+10,inf=1e18; pll a[N]; ll s[3],n,k; ll c[N][3]; deque<ll> dq[3]; int main() { online(); ll ans=1e18; memset(c,0x3f,sizeof c); cin>>n>>k; for(int i=1;i<=n;i++) { char ch; cin>>ch; c[i][0]=c[i-1][0]+1; c[i][1]=c[i-1][1]+1; c[i][2]=c[i-1][2]+1; if(ch=='J') { if(dq[0].size()) s[0]+=i-dq[0].back()-1; dq[0].push_back(i); if(dq[0].size()>k) { ll z=dq[0].front(); dq[0].pop_front(); s[0]-=dq[0].front()-z-1; } if(dq[0].size()==k) { minimize(c[i][0],s[0]); } } if(ch=='O') { if(dq[1].size()) s[1]+=i-dq[1].back()-1; dq[1].push_back(i); if(dq[1].size()>k) { ll z=dq[1].front(); dq[1].pop_front(); s[1]-=dq[1].front()-z-1; } if(dq[1].size()==k) { minimize(c[i][1],c[dq[1].front()-1][0]+s[1]); } } if(ch=='I') { if(dq[2].size()) s[2]+=i-dq[2].back()-1; dq[2].push_back(i); if(dq[2].size()>k) { ll z=dq[2].front(); dq[2].pop_front(); s[2]-=dq[2].front()-z-1; } if(dq[2].size()==k) { minimize(ans,c[dq[2].front()-1][1]+s[2]); } } } if(ans==1e18) ans=-1; cout<<ans; }

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:63:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   63 |             if(dq[0].size()>k)
      |                ~~~~~~~~~~~~^~
ho_t2.cpp:69:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   69 |             if(dq[0].size()==k)
      |                ~~~~~~~~~~~~^~~
ho_t2.cpp:78:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   78 |             if(dq[1].size()>k)
      |                ~~~~~~~~~~~~^~
ho_t2.cpp:84:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   84 |             if(dq[1].size()==k)
      |                ~~~~~~~~~~~~^~~
ho_t2.cpp:93:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   93 |             if(dq[2].size()>k)
      |                ~~~~~~~~~~~~^~
ho_t2.cpp:99:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   99 |             if(dq[2].size()==k)
      |                ~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...