Submission #403340

#	Time	Username	Problem	Language	Result	Execution time	Memory
403340		danielcm585	Painting Walls (APIO20_paint)	C++14	100 / 100	606 ms	14276 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;

const int N = 1e5;
const int M = 5e4;
const int K = 1e5;
int day;
int dp[M+2], vis[M+2];
vector<int> ls[K+2];

/*
dp[x] kontraktor x+i mengerjakan i
for (j : ls[c[i]]) {
    dp[(j-i+n*m)%m]++
    cek
}

for (int i=0;i<N;)

dp[x]++
canTake[i]
dp[x][i] >= M
[i-m+1,i]

dp[x][y-2]
dp[x][y-1]
dp[x][y]

*/

void reset(int x)
{
    if (vis[x] < day-1)
        dp[x] = 0;
    vis[x] = day;
}

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < a[i]; j++)
        {
            ls[b[i][j]].pb(i);
        }
    }
    int last = -1;
    int maks = -1;
    int ans = 0;
    day++;
    for (int i = 0; i < n; i++)
    {
        day++;
        for (int j : ls[c[i]])
        {
            reset((j-i+n)%m);
            dp[(j-i+n)%m]++;
            if (dp[(j-i+n)%m] >= m)
                maks = i;
        }
        if (i == last+m || i == n-1)
        {
            if (maks == last)
                return -1;
            last = maks;
            ans++;
        }
    }
    return (last != n-1 ? -1 : ans);
}

// int main()
// {
//     int N, M, K;
//     cin >> N >> M >> K;
//     vector<int> C(N);
//     for (int i = 0; i < N; i++)
//     {
//         cin >> C[i];
//     }
//     vector<int> A(M);
//     vector<vector<int>> B(M);
//     for (int i = 0; i < M; i++)
//     {
//         cin >> A[i];
//         B[i].resize(A[i]);
//         for (int j = 0; j < A[i]; j++)
//         {
//             cin >> B[i][j];
//         }
//     }
//     cout << minimumInstructions(N,M,K,C,A,B) << '\n';
// }

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37