oj.uz

Submission #198758

# Submission time Handle Problem Language Result Execution time Memory
198758 2020-01-27T13:58:21 Z imaxblue City (BOI06_city) C++17
100 / 100
 13 ms 376 KB 
#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)+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: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.0 / 100.0

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