oj.uz

Submission #965705

# Submission time Handle Problem Language Result Execution time Memory
965705 2024-04-19T05:50:30 Z Pring Painting Walls (APIO20_paint) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {
    const int MXN = 200005, INF = 1e9;
    int n, m, k;
    vector<int> c;
    vector<vector<int>> clr;

    int cid[MXN], worker[MXN];
    bitset<MXN> b, bb;
    int dp[MXN];

    int miku() {
        FOR(i, 0, m) {
            fill(cid + 1, cid + k + 1, -1);
            assert(clr[i].size() == 1);
            cid[clr[i][0]] = i;
        }
        FOR(i, 0, n) {
            if (cid[c[i]] == -1) return -1;
            worker[i] = cid[c[i]];
        }
        FOR(i, 1, n) if ((worker[i - 1] + 1) % m == worker[i]) b[i - 1] = true;
        // FOR(i, 1, n + 1) cout << b[i];
        int ans = 0;
        for (int i = 0, j = 0; i < n; i = ++j) {
            while (b[j]) j++;
            if (j - i + 1 < m) return -1;
            int x = j - i + 1;
            ans += (x - 1) / m + 1;
        }
        return ans;
    }
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    ::n = N;
    ::m = M;
    ::c = C;
    ::clr = B;
    return miku();
}

Compilation message

paint.cpp:30:9: warning: '{anonymous}::dp' defined but not used [-Wunused-variable]
   30 |     int dp[MXN];
      |         ^~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -