Submission #290149

#	Time	Username	Problem	Language	Result	Execution time	Memory
290149		fucking_do_it	Painting Walls (APIO20_paint)	C++14	28 / 100	1588 ms	158976 KiB

paint

#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];
int LCS[inf][2009],dp[inf];
bool valid[inf];
//bool like[2009][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 = 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);

    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);
        //    like[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=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            LCS[i][j] = -1;

    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 (stderr)

paint.cpp: In function 'int solve(int, int)':
paint.cpp:24:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if(idx < Cont[j].size() && Cont[j][idx] == a[i])
      |        ~~~~^~~~~~~~~~~~~~~~

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