/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 2ms 576.0 KiB
#5 Accepted 6ms 660.0 KiB
#6 Accepted 43ms 1.277 MiB
#7 Accepted 42ms 1.234 MiB
#8 Accepted 43ms 1.445 MiB
#9 Accepted 42ms 1.418 MiB
#10 Accepted 1ms 320.0 KiB

Code

#include <bits/stdc++.h>
#define ll long long int
#define ld long double
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(),x.end()
void YES()
{
    cout<<"YES\n";
}
void NO()
{
    cout<<"NO\n";
}
struct Line
{
    ll slope,intercept;
    Line(ll slope , ll intercept) : slope(slope),intercept(intercept){};
    ll value(ll x)
    {
        return x*slope+intercept;
    }
    ll intersection(Line y)
    {
        return ((y.intercept - intercept + slope - y.slope - 1ll) / (slope-y.slope));
    }
    void print()
    {
    	cout<<slope<<" "<<intercept<<" ";
    }
};
struct CHT
{
    deque<pair<Line,ll>> lines;
    void insert(ll m,ll c)
    {
        Line line(m,c);
        while (lines.size() > 1 && lines.back().second >= lines.back().first.intersection(line))
        {
            lines.pop_back();
        }
        if (lines.empty())
        {
            lines.emplace_back(line,0);
            return;
        }
        lines.emplace_back(line,lines.back().first.intersection(line));
        // for (auto i : lines)
        // {
        	// i.first.print();
        	// cout<<i.second<<"\n";
        // }
    }
    ll query(ll x)
    {
        while (lines.size() > 1)
        {
            if (lines[1].first.value(x) > lines[0].first.value(x)) lines.pop_front();
            else break;
        }
        // lines.front().first.print();
        return lines.front().first.value(x);
    }
    ll query2(ll x)
    {
        auto qry = *lower_bound(lines.rbegin(), lines.rend(),
                                make_pair(Line(0, 0), x),
                                [&](const pair<Line, int> &a, const pair<Line, int> &b) {
                                    return a.second > b.second;
                                });
        return qry.first.value(x);
    }
};
const int ALPHABET_SIZE = 26;
struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};
class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& word) {
        TrieNode* current = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (current->children[index] == NULL) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        current->isEndOfWord = true;
    }
    
    void deleteWord(const string& word) {
        deleteWordRecursive(root, word, 0);
    }
    
    bool deleteWordRecursive(TrieNode* node, const string& word, int depth) {
        if (node == nullptr) {
            return false;
        }

        if (depth == word.length()) {
            if (!node->isEndOfWord) {
                return false; // Word not present in the trie
            }

            node->isEndOfWord = false;

            // If the node has no children, it can be safely removed
            return nodeHasNoChildren(node);
        }

        int index = word[depth] - 'a';
        if (deleteWordRecursive(node->children[index], word, depth + 1)) {
            // Delete the child node if it can be deleted
            delete node->children[index];
            node->children[index] = nullptr;

            // Check if the current node has no children and is not an end-of-word node
            return nodeHasNoChildren(node);
        }

        return false;
    }

    bool nodeHasNoChildren(TrieNode* node) {
        for (TrieNode* child : node->children) {
            if (child != nullptr) {
                return false;
            }
        }
        return !node->isEndOfWord;
    }
    
    bool search(const string& word) {
        TrieNode* node = searchNode(word);
        return (node != NULL && node->isEndOfWord);
    }
    
    TrieNode* searchNode(const string& word) {
        TrieNode* current = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (current->children[index] == NULL) {
                return NULL; // Character not found in the trie
            }
            current = current->children[index];
        }
        return current;
    }
    
    void printAllWords() {
        string currentWord;
        printWordsRecursive(root, currentWord);
    }
    
    void printWordsRecursive(TrieNode* node, string& currentWord) {
        if (node == NULL) {
            return;
        }

        if (node->isEndOfWord) {
            cout << currentWord << endl;
        }

        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            if (node->children[i] != NULL) {
                currentWord.push_back('a' + i);
                printWordsRecursive(node->children[i], currentWord);
                currentWord.pop_back();
            }
        }
    }
};

vector<vector<ll>> ST(vector<ll> & a)
{
    ll n = a.size();
    vector<vector<ll>> st(n);
    for (ll e = 0;e<n;e++)
    {
        st[e].push_back(a[e]);
    }
    for (ll k = 1;k<=20;k++)
    {
        for (ll e = 0;e<n-(1<<k)+1;e++)
        {
            st[e].push_back(max(st[e][k-1],st[e+(1<<(k-1))][k-1]));
        }
    }
    return st;
}
vector<ll> twopows;
ll FINDST(vector<vector<ll>> & st,ll l,ll r)
{
    if (twopows.empty())
    {
        twopows = vector<ll>(200001);
        for (ll e = 1,d = 0;e<=200000;e++)
        {
            if ((1 << (d+1)) == e) d++;
            twopows[e] = d;
        }
    }
    ll k = twopows[r-l+1];
    return max(st[l][k],st[r-(1 << k)+1][k]);
}
struct LCT // both queries and lines are sorted in increasing order
{
	ll n;
	vector<Line> tree;
	vector<ll> Q;
	LCT(vector<ll> q)
	{
		Q = q;
		n = q.size()-1;
		tree.assign(4*n+4,Line(0,(ll)-1e18));
	}
	void add(Line curr,ll v = 1,ll l = 1,ll r = -1)
	{
		// cout<<l<<" "<<r<<"\n";
		if (r == -1) r = n;
		if (l == r)
		{
			if (curr.value(Q[l]) > tree[v].value(Q[l])) swap(curr,tree[v]);
			return;
		}
		ll mid = (l+r)/2;
		if (curr.value(Q[mid]) <= tree[v].value(Q[mid]))
		{
			add(curr,v*2+1,mid+1,r);
		}
		else
		{
			swap(tree[v],curr);
			add(curr,v*2,l,mid);
		}
	}
	ll find(ll ind,ll v = 1,ll l = 1,ll r = -1)
	{
		// cout<<tree[v].slope<<" "<<tree[v].intercept<<"\n";
		if (r == -1) r = n;
		if (l == r) return tree[v].value(Q[ind]);
		ll mid = (l+r)/2;
		if (ind <= mid) return max(tree[v].value(Q[ind]),find(ind,v*2,l,mid));
		else return max(tree[v].value(Q[ind]),find(ind,v*2+1,mid+1,r));
	}
};
ll get(ll a,vector<ll> & pr)
{
	return pr[a] = (pr[a] == a ? a : get(pr[a],pr));
}
bool merge(ll a,ll b,vector<ll> & pr,vector<ll> & siz)
{
	 a = get(a,pr),b = get(b,pr);
	 if (a == b) return 0;
	 if (siz[a] > siz[b])
	 {
	 	pr[b] = a;
	 	siz[a] += siz[b];
	 }
	 else
	 {
	 	pr[a] = b;
	 	siz[b] += siz[a];
	 }
	 return 1;
}
mt19937 mt1(time(0));
ld rnd()
{
	ld ANS = mt1();
	ANS /= mt1.max();
	return ANS;
}
void read(vector<ll> & a)
{
	for (ll & i : a) cin>>i;
}
void read(vector<vector<ll>> & a)
{
	for (vector<ll> & i : a)
	{
		for (ll & j : i) cin>>j;
	}
}
void print(vector<ll> & a)
{
	for (ll & i : a) cout<<i<<" ";
	cout<<"\n";
}
void print(vector<vector<ll>> & a)
{
	for (vector<ll> & i : a)
	{
		for (ll & j : i) cout<<j<<" ";
		cout<<"\n";
	}
}
struct BIGINT
{
	vector<ll> a;
	ll len;
	BIGINT(ll n)
	{
		len = n;
		a.assign(n,0ll);
	}
	void add(BIGINT b)
	{
		for (ll e = len-1;e>0;e--)
		{
			a[e] += b.a[e];
			if (a[e] >= 10)
			{
				a[e-1] += 1;
				a[e] -= 10;
			}
		}
	}
	void print()
	{
		bool f = 0;
		for (ll e = 0;e<len;e++)
		{
			if (a[e] > 0) f = 1;
			if (f) cout<<a[e];
		}
		if (!f) cout<<0;
		cout<<"\n";
	}
};
ll mod = 1e9+7;
ll mult(vector<ll> a)
{
	ll answer = 1;
	for (ll i : a)
	{
		answer *= i;
		answer %= mod;
	}
	return answer;
}
ll binpow(ll n,ll k = mod-2)
{
	bitset<31> o(k);
	ll curr = 1;
	for (ll e = 30;e>-1;e--)
	{
		curr *= curr;
		curr %= mod;
		if (o[e])
		{
			curr *= n;
			curr %= mod;
		}
	}
	return curr;
}












void ans()
{
	ll n,d,a,b;cin>>n>>d>>a>>b;
	ll answer = min(n,d)*a+max(0ll,n-d)*b;
	cout<<answer<<"\n";
}
int main()
{
    cin.tie(0);cout.tie(0);
    ios_base::sync_with_stdio(0);
	ll t = 1;cin>>t;
	srand(time(0));
	cout<<fixed<<setprecision(11);
	for (ll e = 1;e<=t;e++)
	{
		ans();
	}
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1090 Summer trip
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 15:51:32
Judged At
2024-11-11 03:02:32
Judged By
Score
100
Total Time
43ms
Peak Memory
1.445 MiB