제출 #548199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548199		farhan132	벽 칠하기 (APIO20_paint)	C++17	100 / 100	831 ms	15996 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
 
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < int, ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define mem(a , b) memset(a, b ,sizeof(a))

const ll N = 1e5 + 5;

ll last[N], p[N];
bool mark[N];
vector < ll > col[N];

int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {

    for(ll i = 0; i < m; i++){
        for(ll j = 0; j < a[i]; j++){
            col[b[i][j]].pb(i);
        }
    }
    mem(last, 0);
    mem(p, 0);
    mem(mark, 0);
    for(ll i = n-1; i >= 0; i--){
        vector < ii > v;
        ll mx = -1;
        for(auto u : col[c[i]]){
            ll nxt = (u + 1)%m;
            if(last[nxt] == i + 1) v.pb({u, p[nxt]});
            else v.pb({u, i}); 
        }
        for(auto [u , val] : v){
            last[u] = i;
            p[u] = val;
            mx = max(val, mx);
        }
        if(mx >= i + m - 1) mark[i] = 1;
    }
    if(!mark[0]) return -1;
    ll st = 0, vis = 0, ans = 1;
    while(st < n){
        ll r = st + m;
        if(r >= n) break;
        ll l = max(vis + 1, st + 1);
        ll c = -1;
        for(ll i = r; i >= l; i--){
            if(mark[i]){
                c = i; break;
            }
        }
        if(c == -1) return -1;
        vis = r;
        st = c;
        ans++;
    }

  return ans;
}

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