oj.uz

Submission #137494

# Submission time Handle Problem Language Result Execution time Memory
137494 2019-07-28T04:53:11 Z gs14004 City (BOI06_city) C++17
100 / 100
 15 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 20005;

lint m;
int t, n, a[MAXN];

lint sum(lint x, lint c){
	return 2 * x * c * (c + 1) + 4 * t * ((c + 1) * c * (c - 1) / 3);
}

pi trial(lint v){
	pi ret(0, 0);
	for(int i=0; i<n; i++){
		if(v < a[i]) break;
		lint cnt = (v - a[i]) / t + 1;
		if(cnt > 1e6){
			ret.first = m + 10ll;
			return ret;
		}
		ret.first += cnt * (cnt + 1) * 2;
		ret.second += sum(a[i], cnt);
	}
	return ret;
}

int main(){
	cin >> m >> t >> n;
	for(int i=0; i<n; i++) scanf("%d",&a[i]);
	lint s = 0, e = 1e14;
	while(s != e){
		lint mi = (s+e+1)/2;
		if(trial(mi).first <= m) s = mi;
		else e = mi-1;
	}
	auto x = trial(s);
	cout << x.second + (m - x.first) * (s + 1) << endl;
}

Compilation message

city.cpp: In function 'int main()':
city.cpp:31:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i]);
                         ~~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 15 ms 632 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct