oj.uz

Submission #463608

# Submission time Handle Problem Language Result Execution time Memory
463608 2021-08-11T11:03:46 Z kilikuma Exam (eJOI20_exam) C++14
0 / 100
 253 ms 2636 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[100000], B[100000];
  int nbSegments =0; 
  Segment seg[100000]; 
  int dp[100000]; 
  for (int i=0;i<100000;i++) {
    dp[i] = 100000; 
  }
  dp[0] = 0; 
  for (int i=1;i<=N;i++) {
    scanf("%d",&A[i]); 
  } 
  for (int i=1;i<=N;i++) {
    scanf("%d",&B[i]); 
  }
  for (int i=1;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); 
  
  for (int iSegment = 0;iSegment < nbSegments; iSegment ++) {
    int dp1[100000]; 
    for (int i=0;i<= nbSegments;i++) dp1[i] = 100000; 
    for (int iCase = 0; iCase <= nbSegments; iCase ++) {
      if (dp[iCase] == 100000) {;}
      else {
        if (seg[iSegment].fin >= dp[iCase]) {
       //   cout << iCase << endl; 
          dp1[iCase+1] = min(dp[iCase+1], seg[iSegment].fin); 
        }
      }
      
    }
    for (int iCase =0; iCase <=nbSegments;iCase ++) {
        if(dp1[iCase] != 100000) 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 2636 KB Output is correct
2 Incorrect 1 ms 2508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 2616 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 2636 KB Output is correct
2 Incorrect 1 ms 2508 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 2636 KB Output is correct
2 Incorrect 1 ms 2508 KB Output isn't correct
3 Halted 0 ms 0 KB -