oj.uz

Submission #569787

# Submission time Handle Problem Language Result Execution time Memory
569787 2022-05-27T19:36:04 Z aryan12 Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 212 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> colors, vector<int> num, vector<vector<int> > likes) 
{
    vector<vector<int> > dp(N, vector<int> (M, -1e9));
    set<int> likings[M];
    for(int contractor = 0; contractor < M; contractor++)
    {
        for(int j = 0; j < num[contractor]; j++)
        {
            likings[contractor].insert(likes[contractor][j]);
        }
    }
    for(int i = N - 1; i >= 0; i--)
    {
        for(int j = 0; j < M; j++)
        {
            if(likings[j].count(colors[i]))
            {
                if(i == N - 1 || dp[i + 1][(j + 1) % M] == -1e9)
                {
                    dp[i][j] = 1;
                }
                else
                {
                    dp[i][j] = dp[i + 1][(j + 1) % M] + 1;
                    dp[i][j] %= M;
                }
            }
            else
            {
                continue;
            }
        }
    }
    vector<int> start_pos;
    for(int i = N - M; i >= 0; i--)
    {
        for(int j = 0; j < M; j++)
        {
            if(dp[i][j] == 0)
            {
                start_pos.push_back(i);
                break;
            }
        }
    }
    int ans = 0;
    int min_x = N - 1;
    for(int i = 0; i < start_pos.size(); i++)
    {
        if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x)
        {
            min_x = start_pos[i];
            ans++;
        }
    }
    return ans + 1;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < start_pos.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
paint.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x)
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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