Submission #924991

#	Time	Username	Problem	Language	Result	Execution time	Memory
924991		adhityamv	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	500 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int INF=1000000000;
int minimumInstructions(int n,int m,int k,vector<int> c,vector<int> a,vector<vector<int>> b){
    vector<int> contractors[k];
    for(int i=0;i<m;i++){
        for(auto j:b[i]){
            contractors[j].push_back(i);
        }
    }
    vector<int> choices[n];
    for(int i=0;i<n;i++){
        for(int j:contractors[c[i]]){
            choices[i].push_back((j+n-1-i)%m);
        }
    }
    bool valid[n]={};
    int cnt[m]={};
    for(int i=0;i<m;i++) for(int j:choices[i]){
        cnt[j]++;
        if(cnt[j]==m) valid[0]=true;
    }
    for(int i=1;i<=n-m;i++){
        for(int j:choices[i-1]){
            cnt[j]--;
        }
        for(int j:choices[i+m-1]){
            cnt[j]++;
            if(cnt[j]==m) valid[i]=true;
        }
    }
    int dp[n];
    if(valid[0]) dp[0]=1;
    else dp[0]=INF;
    multiset<int> prev;
    prev.insert(dp[0]);
    for(int i=1;i<=n-m;i++){
        if(!valid[i]){
            dp[i]=INF;
        } else{
            dp[i]=1+(*prev.begin());
        }
        if(i>=m){
            prev.erase(prev.find(dp[i-m]));
        }
        prev.insert(dp[i]);
    }
    if(dp[n-m]==INF) return -1;
    else return dp[n-m];
}

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