Submission #198758

#	Time	Username	Problem	Language	Result	Execution time	Memory
198758		imaxblue	City (BOI06_city)	C++17	100 / 100	13 ms	376 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
#define startrng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n;
int t, k, a[20005];
ll cnt, ans, cnt2;
bool check(ll M){
  cnt = n; cnt2 = n; ans=0;
  fox(l, k){
    if (M < a[l]) break;
    ll dis = (M-a[l])/t+1;
    if (dis > 1000000) return 1;
    //4td^2+a[l]d -M = 0
    //(-a[l]+sqrt(a[l]^2+16*M*t))/8;
    //ll dis = (-a[l]+sqrt(1LL*a[l]*a[l]+16*M*t))/8/t;
    if (dis <= 0) break;
    //cout << "*" << dis << ' ' << dis*(dis+1)/2*4*a[l] + dis*(dis+1)*(2*dis+1)/6*4*t - dis*(dis+1)/2*4*t << ' ';
    cnt -= dis*(dis+1)/2*4;
    if (M==a[l]+(dis-1)*t) dis--;
    //if ((1LL<<62)-1+(1LL<<62)-ans<dis*(dis+1)/2*4*a[l] - dis*(dis+1)/2*4*t + dis*(dis+1)*(2*dis+1)/6*4*t ||
    //    dis*(dis+1)*(2*dis+1)/6*4 > ((1LL<<62)-1+(1LL<<62))/t) return 1;
    ans += dis*(dis+1)/2*4*a[l] - dis*(dis+1)/2*4*t + dis*(dis+1)*(2*dis+1)/6*4*t;
    cnt2 -= dis*(dis+1)/2*4;
    //cout << cnt << ' ' ;
    //(2x+1)x(x+1)/6
  }
  //cout << endl;
  return cnt<=0;
}
int32_t main(){
  scanf("%lli%i%i", &n, &t, &k);
  fox(l, k){
    scanf("%i", a+l);
  }
  ll lo=1, mid, hi=(500000LL<<20)[phone]LL;
  while(lo<hi){
    //cout << lo << ' ' << hi << endl;
    mid=(lo+hi)/2;
    if (check(mid)) hi=mid;
    else lo=mid+1;
  }
  while(check(lo-1)) lo--;
  check(lo);
  //cout << lo << ' ' << cnt2 << endl;
  //cout << ans << ' ' << cnt << endl;
  cout << ans+cnt2*lo;
  return 0;
}
/*
17 5 4
100
107
114
121
*/

Compilation message (stderr)

city.cpp: In function 'int32_t main()':
city.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lli%i%i", &n, &t, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", a+l);
     ~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100