oj.uz

Submission #568238

# Submission time Handle Problem Language Result Execution time Memory
568238 2022-05-25T02:50:09 Z hibiki Painting Walls (APIO20_paint) C++11
0 / 100
 4 ms 5088 KB 
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second

int n,m,k;
int dp[100100];
deque<int> dq;
vector<int> v[100100];
map<int,int> train;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B)
{
    n = N, m = M, k = K;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < A[i]; j++)
            v[B[i][j]].pb(i);
    dp[n] = 0;
    dq.pb(n);
    for(int i = n - 1; i >= 0; i--)
    {
        bool fi = false;
        map<int,int> temp = train;
        // for(auto val:temp)
        //     printf("%d %d\n",val.f,val.s);
        // printf("---\n");
        train.clear();
        while(dq.back() > i + m)dq.pop_back();
        if(dq.empty())return -1;
        for(int j = 0; j < v[C[i]].size(); j++)
        {
            int cur = v[C[i]][j];
            if(temp[(cur + 1) % m])
                train[cur] = temp[(cur + 1) % m] + 1;
            else
                train[cur] = 1;
            if(train[cur] >= m)
                fi = true;
        }
        if(fi)
        {
            dp[i] = dp[dq.back()] + 1;
            dq.push_front(i);
        }
    }
    if(dp[0] == 0) return -1;
    return dp[0];
}

Compilation message

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Runtime error 4 ms 5088 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Runtime error 4 ms 5088 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Runtime error 4 ms 5088 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Runtime error 4 ms 5088 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Runtime error 4 ms 5088 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -