1659C - Line Empire - CodeForces Solution


brute force dp greedy implementation math

Please click on ads to support us..

Python Code:

def inp(): return int(input())
def strng(): return input().strip()
def jn(x, l): return x.join(map(str, l))
def strl(): return list(input().strip())
def mul(): return map(int, input().strip().split())
def mulf(): return map(float, input().strip().split())
def seq(): return list(map(int, input().strip().split()))
def ceil(x): return int(x) if(x == int(x)) else int(x)+1
def ceildiv(x, d): return x//d if(x % d == 0) else x//d+1

for i in range(inp()):
    n,a,b = mul()
    lst = seq()
    l =[]
    l.append(sum(lst)*b)
    m = []
    s1 =sum(lst)
    a1=0
    for i in range(0,n):
        m.append(s1-lst[i]-a1)
        a1+=lst[i]
    for i in range(0,n):
        c1 = (lst[i]-0)*b+((i+1-n)*lst[i]+m[i])*b
        c2=a*(lst[i]-0)
        if l[0]>(c1+c2):
            l[0]=c1+c2
    print(l[0])

C++ Code:

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) ll a;cin>>a;
#define sin string s;cin>>s;
#define dia di(a)
#define dib di(b)
#define dic di(c)
#define dix di(x)
#define diy di(y)
#define diz di(z)
#define dik di(k)
#define din di(n)
#define dim di(m)
#define diq di(q)
#define endl '\n'
#define precise(i) cout<<fixed<<setprecision(i)
#define V vector<ll>
#define pb push_back
#define M map<ll,ll>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define back(x) x.rbegin(),x.rend()
#define MOD 1000000007
#define db long double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
// const int N =998244353;


int main(){
    fastio;
    

    ll T=1;
    cin>>T;
    // int ogt=0;
    while(T--){
        // ogt++;

        din;
        dia;
        dib;
        V v(n);
        take(v,n);
        ll ans = b*v[0];
        ll curr =0;

        if(a<b*(n-1)) {
            ans += a*v[0];
            curr=v[0];
        }
        for (int i = 1; i < n; ++i)
        {
            if(a<b*(n-1-i)){
                ans += (b+a)*(v[i]-curr);
                curr=v[i];
            }
            else {
                ans += b*(v[i]-curr);
            }
        }

        cout<<ans<<endl;
        
        
        


    }
    return 0;
}   


Comments

Submit
0 Comments
More Questions

702C - Cellular Network
1672C - Unequal Array
1706C - Qpwoeirut And The City
1697A - Parkway Walk
1505B - DMCA
478B - Random Teams
1705C - Mark and His Unfinished Essay
1401C - Mere Array
1613B - Absent Remainder
1536B - Prinzessin der Verurteilung
1699B - Almost Ternary Matrix
1545A - AquaMoon and Strange Sort
538B - Quasi Binary
424A - Squats
1703A - YES or YES
494A - Treasure
48B - Land Lot
835A - Key races
1622C - Set or Decrease
1682A - Palindromic Indices
903C - Boxes Packing
887A - Div 64
755B - PolandBall and Game
808B - Average Sleep Time
1515E - Phoenix and Computers
1552B - Running for Gold
994A - Fingerprints
1221C - Perfect Team
1709C - Recover an RBS
378A - Playing with Dice