oj.uz

Submission #463592

# Submission time Handle Problem Language Result Execution time Memory
463592 2021-08-11T10:45:10 Z kilikuma Exam (eJOI20_exam) C++14
0 / 100
 41 ms 380 KB 
#include <bits/stdc++.h> 
using namespace std;
struct Segment {
  int deb, fin; 
}; 
bool comp(Segment a, Segment b) {
  if (a.deb < b.deb) return (a.deb < b.deb); 
  else return (a.fin < b.fin);
}
int main() {
  int N; 
  scanf("%d",&N); 
  int A[5005], B[5005];
  int nbSegments =0; 
  Segment seg[5005]; 
  int dp[5005]; 
  for (int i=0;i<5005;i++) {
    dp[i] = -1; 
  }
  dp[0] = N+1; 
  for (int i=0;i<N;i++) {
    scanf("%d",&A[i]); 
  } 
  for (int i=0;i<N;i++) {
    scanf("%d",&B[i]); 
  }
  for (int i=0;i<N;i++) {
    for (int j=i; j< N; j++) {
      if (A[j] == B[i]) {
        seg[nbSegments].deb = i; 
        seg[nbSegments].fin = j; 
        nbSegments ++; 
      }
    }
  }
  sort(seg, seg + nbSegments, comp); 
  int dp1[5005]; 
  for (int iSegment = nbSegments-1;iSegment >= 0; iSegment--) {
    for (int i=0;i<5005;i++) dp1[i] = -1; 
    for (int iCase = 0; iCase <= nbSegments; iCase ++) {
      if (dp[iCase] == -1) ; 
      else {
        if (seg[iSegment].fin <= dp[iCase]) {
          dp1[iCase+1] = max(dp[iCase+1], seg[iSegment].fin); 
        }
      }
    }
    for (int iCase =0; iCase <=nbSegments;iCase ++) {
        if(dp1[iCase] != -1) dp[iCase] = dp1[iCase]; 
    }
  }
  int maxi =0; 
  for (int iCase = 0; iCase <= nbSegments; iCase ++) {
    if (dp[iCase] != -1) maxi = max(maxi, iCase); 
  }
  printf("%d\n", maxi); 
}

Compilation message

exam.cpp: In function 'int main()':
exam.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d",&N);
      |   ~~~~~^~~~~~~~~
exam.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d",&A[i]);
      |     ~~~~~^~~~~~~~~~~~
exam.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d",&B[i]);
      |     ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -