Submission #924995

#	Time	Username	Problem	Language	Result	Execution time	Memory
924995		adhityamv	Painting Walls (APIO20_paint)	C++17	100 / 100	947 ms	406188 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;
        }
    }
    if(!valid[n-m]) return -1;
    int ind=n-m;
    int lvi=n-m;
    int ans=1;
    for(int i=n-m;i>=0;i--){
        if(valid[i]) lvi=i;
        if(i==ind-m){
            if(lvi==ind) return -1;
            ind=lvi;
            ans++;
        }
    }
    if(ind!=0 && lvi!=0) return -1;
    if(ind!=0) ans++;
    return ans;
}

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