Submission #567170

#	Time	Username	Problem	Language	Result	Execution time	Memory
567170		Belgutei	Painting Walls (APIO20_paint)	C++17	51 / 100	1574 ms	13856 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define X real()
#define Y imag()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define MOD 1000000007
#define MOD1 1000000009
#define sqr(x) sqr((x)*(x))
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

vector<int> v[100005];
int tur[100005];
int cnt[100005];

ll dp[100005];
 
int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    for(int i = 0; i < M; i ++) {
        for(int j = 0; j < B[i].size(); j ++) {
            // i-th person likes to paint color B[i][j]
            v[B[i][j]].pb(i);
        }
    }
    for(int i = 0; i < N; i ++) dp[i] = 1e9;
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < M; j ++){
            tur[j] = cnt[j];
            cnt[j] = 0;
        }
        bool check = 0;
        for(auto x: v[C[i]]) {
            int pre = x - 1;

            if(pre == -1) pre = M - 1;
            if(tur[pre] + 1 >= M) {
                check = 1;
                cnt[x] = M;
            }
            else {
                cnt[x] = max(cnt[x], tur[pre] + 1);
            }
        }
        
        if(check == 1) {
            if(i == M - 1) {
                dp[i] = 1;
            }
            for(int j = i - 1; j >= max(i - M,0); j --) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    if(dp[N - 1] >= 1e9) return -1;
    return dp[N - 1];
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j = 0; j < B[i].size(); j ++) {
      |                        ~~^~~~~~~~~~~~~

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