Submission #566989

#	Time	Username	Problem	Language	Result	Execution time	Memory
566989		Belgutei	Painting Walls (APIO20_paint)	C++17	28 / 100	80 ms	12560 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))

map<int,bool> mp[1000];
int dp[1005];

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 < B.size(); i ++) {
        for(int j = 0; j < B[i].size(); j ++) {
            mp[i][B[i][j]] = 1;
        }
    }

    for(int i = M - 1; i < N; i ++) {
        int l = i - M + 1;
        int r = i;
        int starter = 0;
        bool check = 0;
        while(starter < M) {
            int cur = starter;
            bool ok = 0;
            for(int j = l; j <= r; j ++) {
                if(mp[cur][C[j]] == 0) {
                    ok = 1;
                    break;
                }
                cur ++;
                if(cur == M) cur = 0;
            }
            if(ok == 0) {
                check = 1;
                break;
            }
            starter ++;
        } 
        if(check == 0) {
            continue;
        }
        if(i == M - 1) {
            dp[i] = 1;
            continue;
        }
        int mn = 1e9;
        for(int j = i - 1; j >= i - M; j --) {
            if(dp[j] == 0) continue;
            mn = min(mn,dp[j]);
        }
        if(mn != 1e9) {
            mn ++;
            dp[i] = mn;
        }
    }
    if(dp[N - 1] == 0) 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:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < B.size(); i ++) {
      |                    ~~^~~~~~~~~~
paint.cpp:24:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int j = 0; j < B[i].size(); j ++) {
      |                        ~~^~~~~~~~~~~~~

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