#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());
int n, 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] < 0) 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("%i%i%i", &n, &t, &k);
fox(l, k){
scanf("%i", a+l);
}
ll lo=1, mid, hi=(500000LL<<20)+2000000000LL;
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
city.cpp: In function 'int32_t main()':
city.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i%i", &n, &t, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
city.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i", a+l);
~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Execution timed out |
1091 ms |
256 KB |
Time limit exceeded |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
6 ms |
376 KB |
Output is correct |
| 5 |
Execution timed out |
1072 ms |
256 KB |
Time limit exceeded |
| 6 |
Correct |
5 ms |
256 KB |
Output is correct |
| 7 |
Execution timed out |
1094 ms |
376 KB |
Time limit exceeded |
| 8 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 9 |
Execution timed out |
1092 ms |
256 KB |
Time limit exceeded |
| 10 |
Correct |
5 ms |
256 KB |
Output is correct |
