/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#include<bits/stdc++.h>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;
template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
output<<"[ ";
if(SZ(v))
{
output<<v[0];
}
FOR(i, 1, SZ(v))
{
output<<", "<<v[i];
}
output<<" ]";
return output;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
output<<"( "<<p.fr<<", "<<p.sc<<" )";
return output;
}
template<typename T>
ostream& operator,(ostream& output, T x)
{
output<<x<<" ";
return output;
}
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
//Header ends here
#define MAXX 2007
int N;
ll ara[MAXX];
ll solve()
{
ll cnt = 0;
sort(ara, ara+N);
for(int i=N-1; i>-1; i--)
{
for(int j=i-1; j>-1; j--)
{
int low = 0, high = j - 1, mid;
while(low <= high)
{
mid = (low+high)/2;
if( ara[mid] + ara[j] > ara[i] )
{
//possible
high = mid - 1;
}
else
{
low = mid + 1;
}
}
cnt += (j - low);
}
}
return cnt;
}
void init()
{
}
int main()
{
init();
int kases, kaseno = 0;
sf("%d", &kases);
while(kases--)
{
sf("%d", &N);
loop(i, N)
{
sf("%lld", &ara[i]);
}
pf("Case %d: %lld\n", ++kaseno, solve());
}
return 0;
}
Category Archives: Binary Search
(lightOj) 1048 – Conquering Keokradong
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
#define MAXX 1003
int main()
{
int kases, kaseno = 0;
take(kases);
int dist[MAXX];
while(kases--)
{
int N, K;
take(N, K);
take(dist[0]);
int low=dist[0], high;
for(int i=1; i<=N; i++)
{
take(dist[i]);
low = max(low, dist[i]);
dist[i] += dist[i-1];
}
high = dist[N];
//for(int i=0; i<=N; i++) pf("dist[%d] = %d\n", i, dist[i]);
int pos, last_value;
while(low<=high)
{
int mid = (low+high)>>1;
//debug(low, mid, high);
last_value = mid;
//dump(mid);
for(int i=0; i<=K; i++)
{
int l = 0, h = N, m;
while(l <= h)
{
m = (l+h)>>1;
if(dist[m] <= last_value)
{
l = m + 1;
}
else
{
h = m - 1;
}
}
pos = l - 1;
//cout<<"\tpos"<<pos<<endl;
last_value = dist[pos] + mid;
if(pos >= N) break;
}
if(pos >= N)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
high++;
pf("Case %d: %d\n", ++kaseno, high);
stack<int>all[302];
last_value = high;
int last_pos = 0;
int s;
for(s=0; s<=K; s++)
{
//dump(last_value);
int l=0, h = N, m;
while(l <= h)
{
m = (l+h)>>1;
if(dist[m] <= last_value)
l = m + 1;
else
h = m - 1;
}
pos = l - 1;
last_value = dist[pos] + high;
for(;last_pos<=pos; last_pos++)
{
all[s].push( dist[last_pos] - (last_pos?dist[last_pos-1]:0) );
}
if(pos>= N) break;
}
for(int i=K; i>-1 && all[i].size() == 0; i--)
{
if(SZ(all[s]) == 0)
s--;
all[i].push(all[s].top());
all[s].pop();
}
for(int i=0; i<=K; i++)
{
int sum = 0;
while(SZ(all[i]))
{
//cout<<all[i].top()<<", ";
sum += all[i].top();
all[i].pop();
}
//cout<<endl<<endl;
pf("%d\n", sum);
}
}
return 0;
}
UnLucky Codes 