#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define make_unique(a) sort(all((a))), (a).erase(unique(all((a))),(a).end())
#define x first
#define y second
#define MP make_pair
#define MT make_tuple
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) FOR(i,1,y) cout << "##"; cout << #x << " = " << x << endl
#define mset(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long i64;
typedef long double ld;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<i64>> vvl;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<i64,i64>> vpll;
int readInt(){ int a; scanf("%d",&a); return a; }
i64 readLong(){ i64 a; scanf("%lld",&a); return a;}
void readString(char *s){ scanf(" %s",s); }
string print(int a){ return to_string(a); }
string print(i64 a){ return to_string(a); }
string print(string a){ return a; }
template<typename T1, typename T2> string print(pair<T1,T2> x){ return "("+print(x.x)+","+print(x.y)+")"; }
template<typename T> string print(vector<T> v){ string ans = "[ "; for(T e : v) ans += print(e)+" "; ans += "]"; return ans; }
template<typename T> string print(T *a, T *b){ string ans = "[ "; while(a!=b) ans += print(*(a++))+" "; ans += "]"; return ans; }
/*
const int mod = 998244353;
int add(int a, int b){ return ((a+=b)>=mod)?a-mod:a; }
int mul(int a, int b){ return a*1ll*b%mod; }
void adding(int &a, int b){ a = add(a, b); }
int pw(int a, int b){
if(a==0) return 0;
int ans = 1, res = a;
for(int i = 1; i <= b; i<<=1, res=mul(res,res)){
if(i&b) ans = mul(ans,res);
}
return ans;
}
*/
const int K = 20005;
i64 cost[K];
int main(){
i64 n, t, k;
scanf("%lld %lld %lld",&n,&t,&k);
FOR(i, 1, k){
scanf(" %lld",&cost[i]);
}
i64 l = cost[1], r = 1e12;
while(l < r){
i64 m = (l+r)/2;
i64 sum = 0;
FOR(i, 1, k){
if(m < cost[i]) break;
i64 number = (m-cost[i])/t+1;
if(number >= 1000000){
sum = n;
break;
}
sum += number*(number+1)*2;
}
if(sum >= n) r = m;
else l = m+1;
}
//printf("[%lld]\n",l);
i64 ans = 0;
i64 sum = 0;
FOR(i, 1, k){
if(l-1 < cost[i]) break;
i64 number = (l-1-cost[i])/t+1;
ans += cost[i]*number*(number+1)*2;
ans += (number*(number-1)*2)*t;
ans += ((number-1)*(number)*(2*number-1)/6)*4*t;
sum += number*(number+1)*2;
}
ans += (n-sum)*l;
assert(sum <= n);
printf("%lld",ans);
return 0;
}
Compilation message
city.cpp: In function 'int readInt()':
city.cpp:31:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | int readInt(){ int a; scanf("%d",&a); return a; }
| ~~~~~^~~~~~~~~
city.cpp: In function 'i64 readLong()':
city.cpp:32:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | i64 readLong(){ i64 a; scanf("%lld",&a); return a;}
| ~~~~~^~~~~~~~~~~
city.cpp: In function 'void readString(char*)':
city.cpp:33:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | void readString(char *s){ scanf(" %s",s); }
| ~~~~~^~~~~~~~~
city.cpp: In function 'int main()':
city.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%lld %lld %lld",&n,&t,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf(" %lld",&cost[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
296 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
9 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
