oj.uz

Submission #290141

# Submission time Handle Problem Language Result Execution time Memory
290141 2020-09-03T12:34:22 Z fucking_do_it Painting Walls (APIO20_paint) C++14
0 / 100
 173 ms 159748 KB 
#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 2e4+9,MX = 1e9+9;
int n,m,k;
int a[inf];
vector<int> Cont[inf],Colors[inf];
int LCS[inf][2009],dp[inf];
bool valid[inf];
unordered_map<int,int> mp[inf];

int solve(int i,int j){

    if( !(j>=1 && j<=m && i>=1 && i<=n) )
        return 0;

    int &ret = LCS[i][j];
    if(ret != -1)
        return ret;
    ret = 0;
    int idx=0;
    /*if(!Cont[j].empty() ){
        idx = lower_bound(Cont[j].begin(),Cont[j].end(),a[i])-Cont[j].begin();
        if(idx < Cont[j].size() && Cont[j][idx] == a[i])
            ret = 1 + solve(i+1,j+1);
    }*/
    if(mp[j][a[i]])
        ret = 1 + solve(i+1,j+1);
    return ret;
}

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=1;i<=n;i++)
        a[i] = C[i-1]+1;
    for(int i=1;i<=m;i++)
        for(auto o:B[i-1])
            /*Cont[i].push_back(o+1),Colors[o+1].push_back(i),*/mp[i][o+1] = 1;
    for(int i=1;i<=m;i++)
            if(!Cont[i].empty())
                sort(Cont[i].begin(),Cont[i].end());

    for(int i=1;i<=k;i++)
        if(!Colors[i].empty())
            sort(Colors[i].begin(),Colors[i].end());

    memset(LCS,-1,sizeof(LCS));

    for(int y=1;y <= n-m+1;y++){
        for(int x = 1;x <= m;x++){
            int len1 = m-x+1,i1 = y,j1 = x,tmp1;
            tmp1 = solve(i1,j1);

            int len2 = x-1,i2 = y+len1,j2 = 1,tmp2 = 0;
            if(len2)
                tmp2 = solve(i2,j2);

            valid[y] |= (tmp1 >= len1 && tmp2 >= len2);
        }
    }
    for(int i=1;i<=n;i++)
        dp[i] = MX;

    dp[n-m+1] = (valid[n-m+1]?1:MX);

    for(int i=n-m;i>=1;i--)
        for(int j=i+1;j<=i+m && valid[i];j++)
            dp[i] = min(dp[i],dp[j] + 1);

    return ( (dp[1] == MX)?-1:dp[1]);
}

Compilation message

paint.cpp: In function 'int solve(int, int)':
paint.cpp:22:9: warning: unused variable 'idx' [-Wunused-variable]
   22 |     int idx=0;
      |         ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 159684 KB Output is correct
2 Correct 99 ms 159648 KB Output is correct
3 Correct 95 ms 159748 KB Output is correct
4 Correct 99 ms 159624 KB Output is correct
5 Correct 92 ms 159736 KB Output is correct
6 Correct 100 ms 159736 KB Output is correct
7 Correct 93 ms 159748 KB Output is correct
8 Correct 101 ms 159736 KB Output is correct
9 Correct 91 ms 159736 KB Output is correct
10 Correct 90 ms 159736 KB Output is correct
11 Correct 117 ms 159740 KB Output is correct
12 Correct 173 ms 159736 KB Output is correct
13 Runtime error 15 ms 4736 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 159620 KB Output is correct
2 Correct 91 ms 159720 KB Output is correct
3 Correct 96 ms 159684 KB Output is correct
4 Correct 99 ms 159648 KB Output is correct
5 Correct 95 ms 159748 KB Output is correct
6 Correct 99 ms 159624 KB Output is correct
7 Correct 92 ms 159736 KB Output is correct
8 Correct 100 ms 159736 KB Output is correct
9 Correct 93 ms 159748 KB Output is correct
10 Correct 101 ms 159736 KB Output is correct
11 Correct 91 ms 159736 KB Output is correct
12 Correct 90 ms 159736 KB Output is correct
13 Correct 117 ms 159740 KB Output is correct
14 Correct 173 ms 159736 KB Output is correct
15 Runtime error 15 ms 4736 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 159620 KB Output is correct
2 Correct 91 ms 159720 KB Output is correct
3 Correct 96 ms 159684 KB Output is correct
4 Correct 99 ms 159648 KB Output is correct
5 Correct 95 ms 159748 KB Output is correct
6 Correct 99 ms 159624 KB Output is correct
7 Correct 92 ms 159736 KB Output is correct
8 Correct 100 ms 159736 KB Output is correct
9 Correct 93 ms 159748 KB Output is correct
10 Correct 101 ms 159736 KB Output is correct
11 Correct 91 ms 159736 KB Output is correct
12 Correct 90 ms 159736 KB Output is correct
13 Correct 117 ms 159740 KB Output is correct
14 Correct 173 ms 159736 KB Output is correct
15 Runtime error 15 ms 4736 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 159620 KB Output is correct
2 Correct 91 ms 159720 KB Output is correct
3 Correct 96 ms 159684 KB Output is correct
4 Correct 99 ms 159648 KB Output is correct
5 Correct 95 ms 159748 KB Output is correct
6 Correct 99 ms 159624 KB Output is correct
7 Correct 92 ms 159736 KB Output is correct
8 Correct 100 ms 159736 KB Output is correct
9 Correct 93 ms 159748 KB Output is correct
10 Correct 101 ms 159736 KB Output is correct
11 Correct 91 ms 159736 KB Output is correct
12 Correct 90 ms 159736 KB Output is correct
13 Correct 117 ms 159740 KB Output is correct
14 Correct 173 ms 159736 KB Output is correct
15 Runtime error 15 ms 4736 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 159620 KB Output is correct
2 Correct 91 ms 159720 KB Output is correct
3 Correct 96 ms 159684 KB Output is correct
4 Correct 99 ms 159648 KB Output is correct
5 Correct 95 ms 159748 KB Output is correct
6 Correct 99 ms 159624 KB Output is correct
7 Correct 92 ms 159736 KB Output is correct
8 Correct 100 ms 159736 KB Output is correct
9 Correct 93 ms 159748 KB Output is correct
10 Correct 101 ms 159736 KB Output is correct
11 Correct 91 ms 159736 KB Output is correct
12 Correct 90 ms 159736 KB Output is correct
13 Correct 117 ms 159740 KB Output is correct
14 Correct 173 ms 159736 KB Output is correct
15 Runtime error 15 ms 4736 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -