Submission #569816

#TimeUsernameProblemLanguageResultExecution timeMemory
569816aryan12Painting Walls (APIO20_paint)C++17
0 / 100
1 ms300 KiB
#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(2, vector<int> (M, -1e9)); vector<int> likings[K]; for(int contractor = 0; contractor < M; contractor++) { for(int j = 0; j < num[contractor]; j++) { likings[likes[contractor][j]].push_back(contractor); } } vector<int> start_pos; for(int i = N - 1; i >= 0; i--) { int omk_cur = i % 2, omk_prev = (i + 1) % 2; bool flag = false; for(int j = 0; j < likings[colors[i]].size(); j++) { int cur = likings[colors[i]][j]; if(i == N - 1 || dp[omk_prev][(cur + 1) % M] == -1e9) { dp[omk_cur][cur] = 1; } else { dp[omk_cur][cur] = dp[omk_prev][(cur + 1) % M] + 1; } if(dp[omk_cur][cur] >= M && i <= N - M && !flag) { start_pos.push_back(i); flag = true; } } // 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; // } // } // // cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n"; // } // cout << "\n\n\n\n"; } // vector<int> start_pos; // for(int i = N - M; i >= 0; i--) // { // for(int j = 0; j < M; j++) // { // if(dp[i][j] >= M) // { // start_pos.push_back(i); // // cout << i << "\n"; // break; // } // } // } int ans = 0; int min_x = N; for(int i = 0; i < start_pos.size(); i++) { // cout << "start_pos[i] = " << start_pos[i] << ", M = " << M << ", minx = " << min_x << "\n"; if(start_pos[i] + M - 1 < min_x - 1) { return -1; } if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x - 1 || start_pos[i] == 0) { min_x = start_pos[i]; ans++; } } if(min_x != 0) return -1; return ans; }

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:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j = 0; j < likings[colors[i]].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < start_pos.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
paint.cpp:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x - 1 || start_pos[i] == 0)
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...