Submission #463608

#	Time	Username	Problem	Language	Result	Execution time	Memory
463608		kilikuma	Exam (eJOI20_exam)	C++14	0 / 100	253 ms	2636 KiB

exam

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

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22