Submission #33849395

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

bitset<3600001> dp[2001]; // bitset 压空间, dp[前i个][值] = 是否可达
int d[2000];
// 旋转矩阵: 逆时针 45度 * 根号2
// (x y) ( 1  1) => (x-y, x+y)
//       (-1  1)
//                                     x y   y   x
// L: (-1 0) => (-1 -1)  =>  +1)/2 => (0,0)  0 + 0 =  0
// D: (0 -1) => ( 1 -1)  =>  +1)/2 => (1,0)  0 + 1 =  1
// U: (0  1) => (-1  1)  =>  +1)/2 => (0,1) 10 + 0 = 10
// R: (1  0) => ( 1  1)  =>  +1)/2 => (1,1) 10 + 1 = 11
const char c[] = { 'L','D','U','R'};
char ans[2010];

bool w(){
  int n = read();
  int x = read();
  int y = read();
  int m[2] = {x-y,x+y};
  int s = 0;
  rep(i,0, n) {
    d[i] = read(); // [1,1800]
    s += d[i];
  }
  rep(i,0,2) if(abs(m[i]) > s) return false; // 过远
  rep(i,0,2) if((m[i] + s) % 2 != 0) return false; // (m[i] + s )/2 = 选部分di
  rep(i,0,2) m[i] = (m[i] + s) / 2;
  dp[0][0] = true;
  rep(i,0, 2000) dp[i + 1] = dp[i] | (dp[i] << d[i]); // 哇
  rep(j,0,2) if(!dp[n][m[j]]) return false; // 有值无法构成
  per(i,0,n){ // 倒着找哪些用了哪些没用
    int bit = 0;
    rep(j,0,2) if (!dp[i][m[j]]) { // 表示可达, 直接贪心选取, 两个中必有一个可行,一个不可行另一个一定可行
      m[j] -= d[i];
      bit += (1 << j);
    }
    ans[i] = c[bit];
  }
  return true;
}

int main() {
  if(!w()) printf("No\n");
  else {
    printf("Yes\n");
    printf("%s\n",ans);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:9:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    9 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result