Submission #759848

#	Time	Username	Problem	Language	Result	Execution time	Memory
759848		1075508020060209tc	Building 4 (JOI20_building4)	C++14	11 / 100	2073 ms	189128 KiB

building4

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ar[1000006];
int br[1000006];

int dp[4010][4010];
int frm[4010][4010];
signed main(){
cin>>n;
for(int i=1;i<=n+n;i++){
    cin>>ar[i];
}
for(int i=1;i<=n+n;i++){
    cin>>br[i];
}
for(int i=1;i<=n+n;i++){
    for(int j=0;j<=n+n;j++){
        dp[i][j]=1e12;
    }
}
dp[1][1]=ar[1];dp[1][0]=br[1];
frm[1][1]=1;
for(int i=2;i<=n+n;i++){
    for(int j=0;j<=n;j++){
        if(j>=1&&ar[i]>=dp[i-1][j-1]){
            dp[i][j]=min(dp[i][j],ar[i]);
            if(dp[i][j]==ar[i]){
                frm[i][j]=1;
            }
        }
        if(br[i]>=dp[i-1][j]){
            dp[i][j]=min(dp[i][j],br[i]);
            if(dp[i][j]==br[i]){
                frm[i][j]=0;
            }
        }
    }
}
if(dp[n+n][n]>=1e12){
    cout<<-1;return 0;
}
vector<int>ans;
int nw=n;
for(int i=n+n;i>=1;i--){
    if(frm[i][nw]==1){
        ans.push_back(1);
        nw--;
    }else{
        ans.push_back(0);
    }
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
    if(ans[i]==0){
        cout<<"B";
    }else{
        cout<<"A";
    }
}


}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:55:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 | for(int i=0;i<ans.size();i++){
      |             ~^~~~~~~~~~~

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