Submission #1156070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156070		reitracn	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	22 ms	19268 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;


signed main()
{
    int N, K;
    scanf("%lld%lld\n", &N, &K);
    vector<int > v(N);
    vector<int > nxt(N, INF);
    vector<deque<int >> deq(3);
    vector<vector<int>> dp(N+1, vector<int>(4, INF));
    for(int iC = 0; iC < N; iC++)
    {
        char carLu;
        scanf("%c", &carLu);
        if(carLu == 'J')
            v[iC] = 0;
        else if(carLu == 'O')
            v[iC] = 1;
        else if(carLu == 'I')
            v[iC] = 2;
        else
            while (true) ;
    }
    for(int pos = 0; pos < N; pos++)
    {
        int colorAct = v[pos];
        deq[colorAct].push_back(pos);

        if(deq[colorAct].size() == K)
        {
            int posFront = deq[colorAct].front();
            deq[colorAct].pop_front();
            nxt[posFront] = pos; 
        }
    }

    /*for(int pos = 0; pos < N; pos++)
    {
        printf("%lld ", nxt[pos]);
    }*/
    dp[0][0] = 0;
    int ans = INF;
    for(int pos = 0; pos< N; pos++)
    {
        for(int state = 0; state < 3; state ++)
        {
            if(state == 0)
                dp[pos+1][state] = min(dp[pos+1][state], dp[pos][state]);
            else
                dp[pos+1][state] = min(dp[pos+1][state], dp[pos][state] + 1);

            if(nxt[pos] != INF && v[pos] == state)
            {
                dp[nxt[pos] +1][state+1] = min(dp[nxt[pos] +1][state+1], dp[pos][state] + (nxt[pos] - pos +1) - K);
                if(state == 2)
                {
                    ans = min(ans, dp[nxt[pos] +1 ][state+1]);
                }
            }
        
        }
    }
    if(ans == INF)
        printf("-1");
    else
        printf("%lld\n", ans);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%lld%lld\n", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%c", &carLu);
      |         ~~~~~^~~~~~~~~~~~~~

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