Submission #445561

#	Time	Username	Problem	Language	Result	Execution time	Memory
445561		sealnot123	City (BOI06_city)	C++14	100 / 100	9 ms	588 KiB

city

#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 (stderr)

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]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100