oj.uz

Submission #908953

# Submission time Handle Problem Language Result Execution time Memory
908953 2024-01-17T03:21:47 Z Boycl07 Painting Walls (APIO20_paint) C++17
0 / 100
 3 ms 4188 KB 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N_ = 1e5 + 4;
const int M_ = 5e4 + 4;
const int K_ = 1e5 + 4;
const int INF = 1e9;


int n, m, k;
vector<int> g[K_];

int cur_len[N_], last_len[N_];
int f[K_], dp[N_];

int minimumInstructions(int n_, int m_, int k_, vector<int> a, vector<int> b, vector<vector<int>> c) {
    n = n_, m = m_, k = k_;
    forn(i, 0, m - 1)
        for(int j : c[i])
            g[j].pb(i);

    deque<int> q;
    q.push_back(0);
    dp[0] = 0;
    rep(i, n)
    {
        for(int j : g[a[i - 1]])
        {
            int j_ = j ? j - 1 : m - 1;
            cur_len[j] = f[j_] ? last_len[j_] + 1 : 1;
        }
        if(i > 1)
            for(int j : g[a[i - 2]])
                f[j] = 0;
        bool can_paint = 0;
        for(int j : g[a[i - 1]])
        {
            f[j] = 1;
            last_len[j] = cur_len[j];
            if(cur_len[j] >= m) can_paint = 1;
        }

        while(sz(q) && i - m > q.front()) q.pop_front();
        if(can_paint)
            dp[i] = dp[q.front()] + 1;
        else dp[i] = INF;
        while(sz(q) && dp[i] < dp[q.back()]) q.pop_back();
        q.push_back(i);
    }
    return dp[n] == INF ? -1 : dp[n];
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 4176 KB Output is correct
7 Correct 3 ms 3928 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 4176 KB Output is correct
7 Correct 3 ms 3928 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 4176 KB Output is correct
7 Correct 3 ms 3928 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 4176 KB Output is correct
7 Correct 3 ms 3928 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 4176 KB Output is correct
7 Correct 3 ms 3928 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -