oj.uz

Submission #924991

# Submission time Handle Problem Language Result Execution time Memory
924991 2024-02-10T10:22:29 Z adhityamv Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 500 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -