oj.uz

Submission #1058351

# Submission time Handle Problem Language Result Execution time Memory
1058351 2024-08-14T09:30:31 Z mispertion Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 2652 KB 
#include "paint.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

#define sz(x) (int)x.size()
#define pb push_back

int n, m, k, ok[N];
vector<int> c, a;
vector<vector<int>> pos, b;
vector<int> dp[N];

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, vector<vector<int>> B) {
    n = N;
    m = M;
    k = K;
    c = C;
    a = A;
    b = B;
    pos.resize(k);
    for(int i = 0; i < m; i++){
        for(auto e : b[i])
            pos[e].pb(i);
    }
    for(int i = 0; i < n; i++){
        dp[i].assign(sz(pos[c[i]]), 1);
        if(sz(dp[i]) == 0)
            return -1;
    }
    if(k == 1)
        return n;
    for(int i = n - 2; i >= 0; i--){
        int ru = 0;
        for(int lu = 0; lu < sz(dp[i]); lu++){
            while(ru < sz(dp[i + 1]) && pos[c[i + 1]][ru] <= pos[c[i]][lu])
                ru++;
            if(ru == sz(dp[i + 1]) || pos[c[i]][lu] + 1 < pos[c[i + 1]][ru])
                continue;
            dp[i][lu] = dp[i + 1][ru] + 1;
        }
        if(pos[c[i]][sz(dp[i]) - 1] == m - 1 && pos[c[i + 1]][0] == 0)
            dp[i][sz(dp[i]) - 1] = dp[i + 1][0] + 1;
        for(auto e : dp[i]){
            if(e >= m)
                ok[i] = 1;
        }
    }
    int ans = 0, r = 0;
    while(r < n){
        int nr = -1;
        for(int l = 0; l < m; l++){
            if(r - l < 0)
                break;
            if(ok[r - l]){
                nr = r - l + m;
                break;
            }
        }
        if(nr == -1)
            return -1;
        ans++;
        r = nr;
    }
    return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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