Submission #444690

#	Time	Username	Problem	Language	Result	Execution time	Memory
444690		ivan_tudor	Building 4 (JOI20_building4)	C++14	100 / 100	331 ms	59644 KiB

building4

#include<bits/stdc++.h>
using namespace std;
struct Interval{
  int l, r;
  Interval(){}
  Interval(int l, int r) : l(l), r(r){}
  Interval operator + (int x) const{
    return Interval{l + x, r + x};
  }
  bool operator == (Interval oth) const{
    return l == oth.l && r ==  oth.r;
  }
  bool contains(int val){
    return l <=val && val <=r;
  }
};
Interval join(Interval a, Interval b){
  Interval nou;
  nou.l = min(a.l, b.l);
  nou.r = max(a.r, b.r);
  return nou;
}
const int N = 1000005;
Interval dp[N][2];
int v[2][N];
Interval IMP(INT_MAX, -INT_MAX);
bool goback(int poz, int val, int nxt){
  if(poz == 0)
    return true;
  if(dp[poz][0].contains(val) && v[0][poz] <= nxt){
    goback(poz -1, val, v[0][poz]);
    cout<<"A";
    return true;
  }
  else if(dp[poz][1].contains(val) && v[1][poz] <= nxt){
    goback(poz - 1, val -1, v[1][poz]);
    cout<<"B";
    return true;
  }
  return false;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i<=2*n; i++){
    cin>>v[0][i];
  }
  for(int i = 1; i<=2*n; i++){
    cin>>v[1][i];

  }
  for(int i = 0; i <= 2* n; i++){
    dp[i][0] = dp[i][1] = IMP;
  }
  dp[0][0] = Interval(0, 0);
  for(int i = 1; i <=2*n; i++){
    for(int k = 0; k <=1; k++){
      if(dp[i-1][k] == IMP)
        continue;
      for(int j = 0; j <=1; j++){
        if(v[j][i] >= v[k][i - 1]){
          if(dp[i][j] == IMP)
            dp[i][j] = dp[i - 1][k] + j;
          else
            dp[i][j] = join(dp[i][j], dp[i - 1][k] + j);
        }
      }
    }
  }
  if(goback(2*n, n, INT_MAX) == false)
    cout<<"-1";
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89