제출 #344881

#제출 시각아이디문제언어결과실행 시간메모리
344881wwdd건물 4 (JOI20_building4)C++14
100 / 100
353 ms79420 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MN = 500500; const ll INFL = 1e18; typedef vector<ll> vl; ll dp[2*MN][2][2]; vl w[2]; bool sur(int id, int pos, int val) { return dp[pos][id][0] <= val && dp[pos][id][1] >= val; } int main() { ios::sync_with_stdio(0);cin.tie(0); ll n; cin >> n; for(int i=0;i<2;i++) { for(int j=0;j<2*n;j++) { ll t; cin >> t; w[i].push_back(t); } } dp[0][0][0] = dp[0][0][1] = 0; dp[0][1][0] = dp[0][1][1] = 1; for(int i=1;i<2*n;i++) { for(int j=0;j<2;j++) { dp[i][j][0] = INFL; dp[i][j][1] = -INFL; for(int k=0;k<2;k++) { if(w[k][i-1] <= w[j][i]) { dp[i][j][0] = min(dp[i-1][k][0]+j,dp[i][j][0]); dp[i][j][1] = max(dp[i-1][k][1]+j,dp[i][j][1]); } } } } int wid; bool poss = false; int rem = n; for(int i=0;i<2;i++) { if(sur(i,2*n-1,n)) { wid = i;poss = true; } } if(poss) { vl res; res.push_back(wid); rem -= wid; for(int i=2*n-1;i>0;i--) { int nid = -1; for(int j=0;j<2;j++) { if(w[j][i-1] <= w[wid][i] && sur(j,i-1,rem)) { nid = j; } } res.push_back(nid); rem -= nid; wid = nid; } reverse(res.begin(),res.end()); for(int i=0;i<res.size();i++) { cout << char(res[i]+'A'); } cout << '\n'; } else { cout << -1 << '\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp: In function 'int main()':
building4.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<res.size();i++) {
      |              ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...