Submission #1315760

#TimeUsernameProblemLanguageResultExecution timeMemory
1315760cosminvixtorGlobal Warming (NOI13_gw)C++20
40 / 40
150 ms6900 KiB
#include <iostream>
using namespace std;

int compare(const void *a, const void *b) {
    int int_a = *(const int *)a;
    int int_b = *(const int *)b;

    if (int_a < int_b) return 1;
    if (int_a > int_b) return -1;
    return 0;
}

void printv(int *A,int n) {
    for (int i=0;i<n;i++) {
        printf("%d ",A[i]);
    }
    printf("\n");
}

int main() {
    int *L,*T,tidx,pidx,vidx,*V,*P,n,i,j,nr,hp,cnt,islands,maxislands;
    scanf("%d",&n);
    L=(int*)calloc(n,sizeof(int));
    T=(int*)calloc(n,sizeof(int));
    j=1;
    scanf("%d",L);
    for (i=1;i<n;i++) {
        scanf("%d",&nr);
        if (nr!=L[j-1]) L[j++]=nr;
    }
    tidx=0;
    if (L[0]>L[1]) {
        T[tidx++]=L[0];
    }
    for (i=1;i<n-1;i++) {
        if (L[i-1]<L[i] && L[i]>L[i+1]) T[tidx++]=L[i];
        else if (L[i-1]>L[i] && L[i]<L[i+1]) T[tidx++]=L[i];
    }
    if (L[n-2]<L[n-1]) {
        T[tidx++]=L[n-1];
    }
    free(L);
    V=(int*)calloc(tidx/2+1,sizeof(int));
    P=(int*)calloc(tidx/2+2,sizeof(int));
    vidx=0; pidx=0;
    for (i=0;i<tidx;i+=2) P[pidx++]=T[i];
    for (i=1;i<tidx;i+=2) V[vidx++]=T[i];
    free(T);
    qsort(P, pidx, sizeof(int), compare);
    qsort(V, vidx, sizeof(int), compare);
    //printv(P,pidx);
    //printv(V,vidx);
    islands=0; maxislands=0; i=0; j=0;
    while (i<pidx || j<vidx) {
        if (P[i]>V[j]) {
            hp=P[i];
            cnt=1;
            while (P[++i]==hp) cnt++;
            islands+=cnt;
        } else {
            hp=V[j];
            cnt=1;
            while (V[++j]==hp) cnt++;
            islands-=cnt;
        }
        if (islands>maxislands) maxislands=islands;
    }
    printf("%d\n",maxislands);
}

Compilation message (stderr)

gw.cpp: In function 'int main()':
gw.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
gw.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d",L);
      |     ~~~~~^~~~~~~~
gw.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d",&nr);
      |         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...