ferinの競プロ帳

競プロについてのメモ

AOJ1604 デッドロック検出

問題ページ
Deadlock Detection | Aizu Online Judge

考えたこと

  • とりあえずサンプルを読む
  • あるスレッドで{1,2}が獲得されてて3を取りたい、別のスレッドで{3}を獲得してて1を取りたい→デッドロック
  • あるuから次のuまでに同じ数字が2回以上出てくる→デッドロック
  • 命令のi番目まで見たときに獲得してるロックの集合と次に取りたいロックのpairを持っておきたい気持ちになる
  • 上をv[i] = (獲得してるロックの集合,次に獲得するロック)としてもつ
  • v[i].second が v[j].first に含まれ、v[j].second が v[i].first に含まれ、 v[i].first と v[j].first が共通要素を持たないならデッドロックが起きている
  • スレッド2個しか使わないのでは(は?)と思ってO(N^2)を書くとサンプルで落ちてる
  • スレッド3個以上でしかデッドロックにならない場合は当然ある
  • 命令のi番目まで実行していて次の命令を実行したい
  • このとき命令のj番目まで実行しているスレッドがあると実行できないなら i->j の辺を張る
  • このグラフ上で閉路が存在したらデッドロックが起きる気がする
  • 有向グラフのループ検出なのでトポロジカルソートをする
  • 出すと落ちる
  • スレッドは最大10個しかないので長さ11以上の閉路があったとしてもデッドロックにはならない
  • トポロジカルソートでループに入ってる頂点はわかるのでその頂点集合についてUFで連結成分ごとに分ける
  • ループごとの長さが分かる気がしたのでこれで出すと落ちる
  • 冷静に考えると閉路がくっついているようなパターンがあって無理
  • これ高速にするの無理そう
    -------解説を見た-------
  • 獲得しているロックの集合Sと次に取るロックがtという状態を取りうるか?
  • dp[S][t] = (true or false) みたいなDP配列を考える
  • dp[s1][t1] = dp[s2][t2] = true で s1とs2の共通部分が存在せず、t1 が s2に属するとき dp[s1 | s2][t2] = true も成り立つ
  • 上で考えた通り s1とs2の共通部分が存在せず、t1 が s2に属し、t2 が s1 に属するとき デッドロックが生じる
  • dp配列を更新しつつデッドロックが起きる状態があるか確認していく

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

int dp[1<<10][10];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    string s;
    cin >> s;

    memset(dp, false, sizeof(dp));
    int now = 0;
    bool safe = true;
    REP(i, n) {
      if(s[i] == 'u') now = 0;
      else {
        dp[now][s[i]-'0'] = true;
        if(now & 1<<(s[i]-'0')) {
          safe = false;
          break;
        }
        now |= 1<<(s[i]-'0');
      }
    }

    if(!safe) {
      cout << "UNSAFE" << endl;
      continue;
    }

    REP(s1, 1<<10) REP(t1, 10) {
      if(!dp[s1][t1]) continue;
      // dp[s1][t1] と マージ
      REP(s2, 1<<10) REP(t2, 10) {
        if(!dp[s2][t2]) continue;
        bool cond1 = !(s1&s2) && (s2 & 1 << t1),
             cond2 = !(s1&s2) && (s1 & 1 << t2);
        if(cond1 && cond2) {
          safe = false;
        } else if(cond1) {
          dp[s1 | s2][t2] = true;
        } else if(cond2) {
          dp[s1 | s2][t1] = true;
        }
      }
    }

    if(safe) cout << "SAFE" << endl;
    else cout << "UNSAFE" << endl;
  }

  return 0;
}

AOJ2585 一日乗車券

問題ページ 1 Day Passport | Aizu Online Judge

考えたこと

  • とりあえず入力で何がくるのかちゃんと読む
  • 会社の数の制約が小さい
  • dp[S] = (会社の集合Sを乗り放題にするために必要な最小コスト) を求めておく
  • これは簡単なbitDPでできてO(2^KP)
  • 会社の集合Sが乗り放題のときに s->t に行くかかる時間がh以下の最小のコストを求めたい
  • d[i][j] = (頂点iまでに時間jかかったときの最小コスト) として拡張dijkstra
  • 全ての集合Sに対して拡張dijkstraをするのでO(2^KMlogNH) になる
  • 計算量が問題なさそうなので出すと通った

典型詰め合わせセットみたいな問題

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct edge { int to, cost, time, com; };

vector<edge> g[105];
int dp[1<<8], ticket[1<<8], fee[1<<8];
int d[105][30];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m, h, k;
    cin >> n >> m >> h >> k;
    if(!n) break;
    REP(i, 1<<k) dp[i] = ticket[i] = fee[i] = 0;
    REP(i, n) g[i].clear();
    REP(i, m) {
      int a, b, c, h, r;
      cin >> a >> b >> c >> h >> r;
      a--, b--;
      g[a].PB({b, c, h, r-1});
      g[b].PB({a, c, h, r-1});
    }
    int s, t;
    cin >> s >> t; s--, t--;
    int p;
    cin >> p;
    REP(i, p) {
      int l;
      cin >> l >> fee[i];
      REP(j, l) {
        int com;
        cin >> com; com--;
        ticket[i] |= 1<<com;
      }
    }

    REP(i, 1<<k) dp[i] = INF;
    dp[0] = 0;
    REP(i, 1<<k) REP(j, p) chmin(dp[i | ticket[j]], dp[i] + fee[j]);

    int ans = INF;
    REP(i, 1<<k) {
      // iの会社はただで使えるとする
      int ret = dp[i];

      REP(j, 105) REP(l, 30) d[j][l] = INF;
      d[s][0] = 0;
      priority_queue<VI, VVI, greater<VI>> que;
      que.push({d[s][0], s, 0});

      while(que.size()) {
        VI v = que.top(); que.pop();
        if(v[1] == t) break;
        for(edge e: g[v[1]]) {
          int n_cost = d[v[1]][v[2]] + (i & 1 << e.com ? 0 : e.cost);
          if(v[2] + e.time <= h && d[e.to][v[2]+e.time] > n_cost) {
            d[e.to][v[2]+e.time] = n_cost;
            que.push({d[e.to][v[2]+e.time], e.to, v[2]+e.time});
          }
        }
      }

      int mi = INF;
      REP(j, h+1) chmin(mi, d[t][j]);
      chmin(ans, ret+mi);
    }

    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
  }

  return 0;
}

yukicoder No.685 Logical Operations

問題ページ
No.685 Logical Operations - yukicoder

考えたこと

  • bitだし2進数で考える
  • x AND y, x XOR y, x OR y を書いてみる
X 01001
Y 11101

& 01001
^ 10100
| 11101
  • x,yのi桁目を(x_i,y_i)と表す
  • AND < XOR を満たすためには1が出てくる最初の桁が(0,1)であることが必要
  • XOR < OR を満たすためにはどこかに(1,1)が必要
  • N <= 10^18 で条件を満たす数の数え上げ→大体桁DP
  • dp[i桁目][j(N未満が確定しているか)][(1,1)の存在][(0,1)が先頭にあるか] のDP
  • (0,1)の先頭はまだ1がでていなければ0、(0,1)が先頭なら1、それ以外が先頭なら2とする
  • dp[i][j][k][l] からの遷移について考える
  • (0,0)(0,1)(1,0)(1,1) の4通りが遷移としてある
  • (0,0) であれば dp[i+1][j || 0<(nのi桁目)][k][l]
  • (1,0) では x <= y の条件から (0,1) が前の桁で出ていることが必要で dp[i+1][j || 0<(nのi桁目)][k][l] となる
  • (0,1) では y <= n の条件からyのi桁目を1にできることが必要で dp[i+1][j][k][l==0?1:l]
  • (1,1) でも y <= n の条件からyのi桁目を1にできることが必要で dp[i+1][j][1][l==0?2:l]
  • 遷移が全て書けたのでこれにしたがって桁DPを書く

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[65][2][2][3];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  // nを2進数にしたときの桁数
  int m = 0, n_ = n;
  while(n_ > 0) {
    m++;
    n_ /= 2;
  }

  dp[0][0][0][0] = 1;
  REP(i, m) REP(j, 2) REP(k, 2) REP(l, 2) {
    if(dp[i][j][k][l] == 0) continue;
    int lim = j?1:(n>>(m-i-1)&1);
    // (0,0)
    (dp[i+1][j || 0<lim][k][l] += dp[i][j][k][l]) %= MOD;
    // (1,0)
    if(l == 1) (dp[i+1][j || 0<lim][k][l] += dp[i][j][k][l]) %= MOD;
    if(lim == 1) {
      // (0,1)
      int cond = l==0?1:l;
      (dp[i+1][j][k][cond] += dp[i][j][k][l]) %= MOD;
      // (1,1)
      cond = l==0?2:l;
      (dp[i+1][j][1][cond] += dp[i][j][k][l]) %= MOD;
    }
  }

  int ans = 0;
  REP(i, 2) (ans += dp[m][i][1][1]) %= MOD;
  cout << ans << endl;

  return 0;
}

AOJ1330 Never Wait for Weights

問題ページ
Never Wait for Weights | Aizu Online Judge

考えたこと

  • bがaよりwグラム重いことを頂点bから頂点aへ重みがwの辺を張ることで表す
  • すると重さの差の質問クエリがある頂点からある頂点までの距離を求めるクエリに帰着できる
  • 重さの差を測るクエリは辺を張ることで表す
  • 質問クエリでその時点で2頂点が連結なら距離は絶対にわかる
  • 逆に非連結なら"UNKNOWN"になる
  • 余計に辺が張ってあったとしても関係ないのでクエリ先読みして辺を張っておいてよい
  • 問題設定からすでに連結している2頂点間で辺を張るようなクエリは無視できる
  • 無視できるクエリについて辺を張らないとするとグラフは森になる
  • 森で2点間の距離を高速に求めるクエリ→LCAでよさそう
  • 辺の重みの正負がその辺と逆辺で反対になるのに注意しつつ考える
  • いつものLCAみたいに考えると d[u] + d[v] - d[lca]*2 だけど上の通りこれはおかしい
  • vの方は正負が反転して (d[u] - d[lca]) - (d[v] - d[lca]) となる
  • lcaの部分が消えてd[u]-d[v]となる
  • つまり実はLCAが要らなくてdfsで根からの距離を求めればいいだけ

考察するとdfsするだけになって面白い

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const ll LLINF = (1LL<<60);

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int s[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

vector<PII> g[100010];
int d[100010];
void dfs(int x, int p, int dist) {
  d[x] = dist;
  for(auto e: g[x]) {
    if(e.first != p) dfs(e.first, x, dist + e.second);
  }
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m;
    cin >> n >> m;
    if(!n) break;

    REP(i, n) g[i].clear();
    memset(d, 0, sizeof(d));
    uf.init(n);

    vector<PII> query;
    VI ans(m+5);
    int idx = 0;
    REP(i, m) {
      char c;
      int a, b;
      cin >> c >> a >> b; a--, b--;
      if(c == '!') {
        int w; cin >> w;
        if(!uf.same(a, b)) {
          uf.unite(a, b);
          g[a].PB({b, -w});
          g[b].PB({a, w});
        }
      } else {
        query.PB({a, b});
        if(!uf.same(a, b)) ans[idx] = LLINF;
        idx++;
      }
    }

    REP(i, n) if(d[i] == 0) dfs(i, -1, 0);

    REP(i, query.size()){
      if(ans[i]==LLINF) cout << "UNKNOWN" << endl;
      else cout << d[query[i].first] - d[query[i].second] << endl;
    }
  }

  return 0;
}

AOJ2200 Mr. Rito Post Office

問題ページ
Mr. Rito Post Office | Aizu Online Judge

考えたこと

  • 人がx、船がyにある状態を(x,y)と書くことにする
  • ある頂点aにいるとき考えられる状態は (a,1)(a,2)(a,3)…(a,n) のN通り
  • 頂点aから頂点bに移動するとき(a,1)→(b,1)(b,2)…(b,n)、(a,2)→(b,1)(b,2)…(b,n) … のN^2通りの移動方法がある
  • (a,x) → (b,y) への移動にかかる最短距離がO(1)でわかればO(N^2R)で解ける
  • 3*10^7くらいでそれっぽい計算量
  • 前計算で最短距離を求められるようにしておきたい
  • d[i][j] = ((i,j)に到達するまでの最短距離) として拡張dijkstraをするとできそう
  • 計算量について考えると始点がO(N^2)でdijkstraがO(MlogN)あるので全体でO(N^2MlogN)
  • これはTLEしそう
  • 陸と海で別々に考えられないか?
  • (a,x) → (b,y) へ移動するときに海を使うとする
  • そのときは 陸でaから船があるxまで行く→海でyまで行く→陸でyからbまで行くと移動するのが最適
  • x=yであれば海を使わないことも可能でそれならば陸でaからbまで行く
  • 陸と海の道でそれぞれ最短経路を求めることができれば(a,x) → (b,y) の最短距離がわかる
  • これはワーシャルフロイドを用いてO(N^3)で解ける
  • したがって全体で O(N^3+N^2R) で解ける

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

const int INF = (1LL<<30);

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int d1[205][205], d2[205][205];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  to_string(123);

  while(true) {
    int n, m;
    cin >> n >> m;
    if(!n) break;
    REP(i, n) REP(j, n) {
      d1[i][j] = i==j?0:INF;
      d2[i][j] = i==j?0:INF;
    }
    REP(i, m) {
      int x, y, c;
      char t;
      cin >> x >> y >> c >> t;
      x--, y--;
      if(t == 'L') {
        chmin(d1[x][y], c);
        chmin(d1[y][x], c);
      } else {
        chmin(d2[x][y], c);
        chmin(d2[y][x], c);
      }
    }

    REP(k, n) REP(i, n) REP(j, n) {
      chmin(d1[i][j], d1[i][k] + d1[k][j]);
      chmin(d2[i][j], d2[i][k] + d2[k][j]);
    }

    int r;
    cin >> r;
    VI cur(n, INF), nxt(n, INF);
    int now;
    cin >> now; now--;
    REP(i, n) cur[i] = i==now?0:INF;
    REP(i, r-1) {
      int g;
      cin >> g; g--;

      REP(j, n) {
        // (now, j) からスタートする
        REP(k, n) {
          // (g, k) を目的とする
          // 陸でnow->j 船でj->k 陸でk->g
          int tmp = d1[now][j] + d2[j][k] + d1[k][g];
          // 陸だけで移動
          if(j == k) chmin(tmp, d1[now][g]);
          chmin(nxt[k], cur[j] + tmp);
        }
      }

      cur = nxt;
      nxt.assign(n, INF);
      now = g;
    }

    int ret = INF;
    REP(i, n) chmin(ret, cur[i]);
    cout << ret << endl;
  }

  return 0;
}

GCJ 2018 round1 C - A Whole New Word

問題ページ Google Code Jam

考えたこと

  • 全ての可能な単語パターンは何通りか
  • i文字目の文字種をc[i]とするとc[i]の総積になる
  • nがこれに等しければ何をつくっても一致するので不可能
  • とりあえず適当にケースをつくってみる
  • j文字目が全て同じ文字→j文字目を異なるものにできない
  • j文字目に異なる文字が含まれるのが1列だけ→新たな単語をつくることはできない
ABC
ABD
ABE
  • 何か実験してると1文字交換して不可能で2文字交換するとできるみたいなパターンがなさそう
  • 1文字置換ならば全探索してもO(N^2LlogN)くらいになりそう
  • 全ケース最悪なパターンが来るとちょっと怪しい気持ちになる
  • 答えが見つかったタイミングで終了してるから最悪になるケースはそんななさそう
  • 単語iに単語jの文字を移したとしても新たな単語が作れないときを考えるとAAAA,AAAB,AAAC,AAAD,…,AAAZみたいな感じでそんなに個数がなさそう
  • 何とかなりそうなので出すと通った

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int testcase;
  cin >> testcase;
  REP(tes, testcase) {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    REP(i, h) cin >> s[i];

    set<string> st;
    REP(i, h) st.insert(s[i]);

    string ans = "-";
    REP(i, h) REP(j, h) {
      if(i == j) continue;
      REP(k, w) {
        if(s[i][k] != s[j][k]) {
          string tmp = s[i];
          tmp[k] = s[j][k];
          if(st.find(tmp) == st.end()) {
            ans = tmp;
            goto end;
          }
        }
      }
    }

    end:;
    cout << "Case #" << tes+1 << ": " << ans << endl;
  }

  return 0;
}

AOJ2642 Dinner

問題ページ
Dinner | Aizu Online Judge

考えたこと

  • すべての日で自炊するとする
  • このときの幸福度は簡単に求まる
  • ある日を自炊から外食に変えると変化する幸福度は(外食の幸福度)-(その日の自炊の分)-(その日以降で自炊する日数)*(定数)
  • i日目以降で自炊をj回するときの幸福度の最大値をdp
  • これはO(N^2)で無理
  • 自炊をi回するときに最適な選び方は何か
  • 連続で選ぶとマイナスされる前に自炊で稼げる
  • できるだけ外食が低いときに自炊したい
  • 自炊の回数と幸福度について単調性→ない
  • 凸性→なさそう
  • i日目までで最後に自炊をしたのがj日目でDP
  • これもN^2で無理ゲー
  • i日目に得られる幸福度が高い行動をする貪欲
  • 1回目の自炊よりは外食が高いけど後々のために自炊しといた方がいいパターン
  • i回自炊をするときの日付の集合がi+1回自炊をするときの日付の部分集合になってて貪欲に選べるみたいな?
  • 1回自炊をするときは3日目を選ぶけど2回自炊をするときは1日目と4日目を選んだほうが最適みたいなのが存在しない気持ちになる
  • i回自炊するときの幸福度をi-1回自炊するときの幸福度を元にそれぞれO(1)で求められればO(N)でできそう
  • 0回自炊をするときの幸福度はO(N)で簡単に求まる
  • 自炊の回数を0回→1回にするときでi日目を自炊に変化させるときの幸福度の変化を考える
  • これは -(外食の幸福度) + (自炊パワーの初期値+i)*(定数) になる
  • これも各日についてO(N)あれば求まる
  • i日目を自炊にするとき他の日の幸福度の変化がどう変わるか
  • i日目より後の日→自炊パワーが-1されていた状態から+1される状態になる→+2P
  • i日目より前の火→i日目の自炊で得られる幸福度がプラスされる→上と同じで+2P
  • したがって一回自炊をする日を増やすと他の日の幸福度の変化に+2Pされる
  • 外食→自炊に変化させる日は幸福度の変化が最大の日を貪欲に選べばよい
  • ソートする部分が一番重くO(NlogN)で間に合いそう

やることは最終的にソートして貪欲だけど考察が大変
複数の操作があるときに全ての項目に対してある片方の操作をすると考えてもう片方に変えるときにどう変化するか
昔やったつるかめ算を思い出す

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, p, q;
  cin >> n >> p >> q;
  VI c(n);
  REP(i, n) cin >> c[i];

  int ret = 0;
  REP(i, n) ret += c[i];

  VI v;
  int now = q;
  REP(i, n) {
    v.PB(p*now-c[i]);
    now--;
  }
  sort(ALL(v), greater<>());

  now = 0;
  int ans = ret;
  REP(i, n) {
    ret += v[i] + now;
    chmax(ans, ret);
    now += 2*p;
  }
  cout << ans << endl;

  return 0;
}