Submission #1217929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217929		asdfghqwert	City (BOI06_city)	C++20	90 / 100	1097 ms	8544 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);
    priority_queue< pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
    vector<int> rng(1e6);
    int n, t , k , ans = 0;
    cin >> n >> t >> k;
    vector<int> ds(k + 1);
    for(int i = 1 ;i <= k ; i++)cin >> ds[i];
    rng[0] = 1e9;
    pq.push({ds[1] , 1});
    while(true){
        int value = pq.top().first , idx = pq.top().second , cmt = idx * 4;
        pq.pop();
        if(n <= cmt){
            ans += n * value;
            break;
        }else{
            ans += cmt * value;
            n -= cmt;
        }
        if(rng[idx + 1] == rng[idx])pq.push({value + t , idx + 1});
        rng[idx]++;
        if(rng[idx] != rng[idx - 1] && rng[idx] < k )pq.push({ds[rng[idx] + 1] + t * (idx - 1) , idx});
    }
    cout << ans;
}

• Subtask 1: 90 / 100