Submission #1020056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020056		salmon	Watching (JOI13_watching)	C++14	100 / 100	576 ms	18120 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int N,P,Q,h,s,e,w,temp,bi,si,flag,flog;
int lst[2100];
multiset<int> sor;
multiset<int>::iterator ii;
int bjump[2100];
int sjump[2100];
int deepee[2100][2100];

int dp(int i, int p){
    if(i == -1){
        flog = 1;
        return 0;
    }

    if(deepee[i][p] != -1){
        return deepee[i][p];
    }

    //printf("%d %d\n",i,p);

    if(p == 0){
        deepee[i][p] = dp( bjump[i], p) + 1;
        return dp( bjump[i], p) + 1;
    }
    else{
        deepee[i][p] = min( dp( bjump[i], p) + 1, dp(sjump[i] , p - 1) );
        return min( dp( bjump[i], p) + 1, dp(sjump[i] , p - 1) );
    }

}


int main(){
    memset(lst,-1,sizeof(int) * 2100);
    scanf(" %d",&N);
    scanf(" %d",&P);
    scanf(" %d",&Q);
    for(int i = 1; i <= N; i++){
        scanf(" %d",&h);
        sor.insert(h);
    }

    for(int i = 1; i <= N; i++){
        ii = sor.end();
        advance(ii,-1);
        lst[i] = *ii;

        sor.erase(ii);
    }

    if(Q + P >= N){
        printf("1");
        return 0;
    }

    s = 1;
    e = 1000000000;
    w = (s + e)/2;

    while(w != temp){

        memset(deepee,-1,sizeof(int) * 2100 * 2100);
        memset(sjump,-1,sizeof(int) * 2100);
        memset(bjump,-1,sizeof(int) * 2100);
        si = 1;
        bi = 1;
        for(int i = 1; i <= N; i++){
            while(lst[si] != -1){
                if(lst[si] < lst[i] - w + 1){
                    break;
                }
                si = si + 1;
            }

            while(lst[bi] != -1){
                if(lst[bi] < lst[i] - w - w + 1){
                    break;
                }
                bi = bi + 1;
            }

            if(lst[bi] == -1){
                bjump[i] = -1;
            }
            else{
                bjump[i] = bi;
            }

            if(lst[si] == -1){
                sjump[i] = -1;
            }
            else{
                sjump[i] = si;
            }
        }

        flog = 0;
        flag = dp(1,P);
        //printf(" return = %d\n",flag);
        if(flag <= Q && flog == 1){
            e = w;
        }
        else{
            s = w + 1;
        }

        //printf("%d %d %d\n",w,(s+e)/2,flag <= Q);
        temp = w;
        w = (s + e)/2;

        /*for(int i = 0; i <= N; i++){
            printf("%d ",sjump[i]);
        }
        printf("\n");

        for(int i = 0; i <= N; i++){
            printf("%d ",bjump[i]);
        }
        printf("\n");



        for(int i = 0; i <= N; i++){
            for(int ii = 0; ii <= P; ii++){
                printf("%d ",deepee[i][ii]);
            }
        printf("\n");
        }
        printf("\n");*/
    }
    printf("%d",w);
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
watching.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf(" %d",&P);
      |     ~~~~~^~~~~~~~~~
watching.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
watching.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50