Submission #1217866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217866		asdfghqwert	City (BOI06_city)	C++20	10 / 100	19 ms	16200 KiB

city

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define int unsigned long long int
using namespace std;
typedef unsigned long long ll;

const int T = 350;
const int MOD = 1e9 + 7;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , t , k;
    cin >> n >> t >> k;
    vector<int> ds(k + 1);
    for(int i = 1 ; i <= k ; i++)cin >> ds[i];
    vector<int> rng(1e6);
    vector<int> fstrng(1e6);
    fstrng[0] = 1;
    int ans = 0;
    while(true){
        int bestdeal = 0 , best_valu = 1e18;
        for(int i = 0 ;i < k ; i++){
            if(fstrng[i] == 0)continue;
            if(ds[i + 1] + (fstrng[i] - 1) * t <= best_valu){
                best_valu = ds[i + 1] + (fstrng[i] - 1) * t;
                bestdeal = i;
            }
        }
        int cmt = (1ll << (1 + fstrng[bestdeal]));
        if(n <= cmt){  
            ans += n * best_valu;
            break;
        }else{
            ans += cmt * best_valu;
            n -= cmt;
        }
        if(fstrng[bestdeal + 1] == 0)fstrng[bestdeal + 1] = fstrng[bestdeal];
        if(rng[fstrng[bestdeal] + 1] == bestdeal)fstrng[bestdeal]++;
        else fstrng[bestdeal] = 0;
        rng[fstrng[bestdeal]]++;
    }
    cout << ans << '\n';
}

• Subtask 1: 10 / 100