Educational Codeforces Round 16 - Problem E

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

#define ff(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define fod(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define ll long long
#define pb push_back
#define x first
#define y second
typedef pair <int, int> ii;
typedef vector <int> vi;
const int N = 10000010, INF = (int)1e9, mod = (int)1e9 + 7;

ll n, x, y;
ll f[N];
deque <int> q;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) {
        int t = i % 2; f[i] = f[i-1] + x;
        ll r = 1e17;
        while(!q.empty() && q.front() < ((i + 1) / 2)) q.pop_front();
        if (!q.empty()) r = f[q.front()] + 2 * q.front() * x;
        f[i] = min(f[i], r + y - i * x);
        while(!q.empty() && f[q.back()] + 2 * q.back() * x >= f[i] + 2 * i * x) q.pop_back();
        q.push_back(i);
    }
    cout << f[n] << endl;
}