oj.uz

답안 #123249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123249 2019-06-30T18:01:50 Z rajarshi_basu 쌀 창고 (IOI11_ricehub) C++14
68 / 100
 1000 ms 119252 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>

#include "ricehub.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define il pair<int,ll>
#define li pair<ll,int>
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,ll>
#define vv vector

using namespace std;

const ll INF = 1e16+10;
const int MAXN = 100*100*10+10;
const int MAXVAL = 1e9+10;

struct Node{
	int left;
	int right;
	ll p1;
	int p2;
	Node(){
		left = -1;
		right = -1;
		p1 = 0;
		p2 = 0;
	}
	void init(){
		left = -1;
		right = -1;
		p1 = 0;
		p2 = 0;
	}
};
Node B[(int)5*1000*1000];
int PTR= 0;
int get__(){
	B[++PTR].init();
	//cout << PTR << endl;
	return PTR;
}
struct Segtree{

	

	int head = get__();
	inline void expand(int node){
		if(B[node].left == -1)B[node].left = get__();
		if(B[node].right == -1)B[node].right = get__();
	}
	void update(int node,int ss,int se,int i,ll val){
		if(i > se or i < ss)return;
		expand(node);
		//cout << node << endl;
		if(ss==se){
			B[node].p1 += val;
			B[node].p2 += 1;
			return;
		}
		int mid = (ss+se)/2;
		update(B[node].left,ss,mid,i,val);
		update(B[node].right,mid+1,se,i,val);
		B[node].p1 = B[B[node].left].p1 + B[B[node].right].p1;
		B[node].p2 = B[B[node].left].p2 + B[B[node].right].p2;
	}
	li get(int node,int ss,int se,int l,int r){
		if(node == -1)return {0,0};
		if(l > se or ss > r)return {0,0};
		if(l <= ss and se <= r)return {B[node].p1,B[node].p2};
		int mid = (ss+se)/2;
		li a = get(B[node].left,ss,mid,l,r);
		li b = get(B[node].right,mid+1,se,l,r);
		return {a.ff+b.ff,a.ss+b.ss};
	}
};
Segtree st;
int besthub(int r,int l,int h[],ll b){

	FOR(i,r){
		st.update(st.head,0,MAXVAL,h[i],h[i]);
	}
	int best = 1;

	FOR(i,r){
		int lo = 0;
		int hi = l+10;
		while(lo <= hi){
			int mid = (lo+hi)/2;

			if(hi - lo < 0){
				FORE(j,lo,hi){
					li cost1 = st.get(st.head,0,MAXVAL,h[i],min(h[i]+j,MAXVAL-1));
					cost1.ff -= (ll)h[i]*cost1.ss;

					li cost2 = st.get(st.head,0,MAXVAL,max(h[i]-j,0),h[i]-1);
					cost2.ff = (ll)h[i]*cost2.ss - cost2.ff;

					if(cost2.ff + cost1.ff <= b){
						best = max(best,cost1.ss+cost2.ss);
					}
				}				
				break;
			}


			int s = h[i]-mid;
			int e = h[i]+mid;

			li cost1 = st.get(st.head,0,MAXVAL,h[i],min(h[i]+mid,MAXVAL-1));
			cost1.ff -= (ll)h[i]*cost1.ss;

			li cost2 = st.get(st.head,0,MAXVAL,max(h[i]-mid,0),h[i]-1);
			cost2.ff = (ll)h[i]*cost2.ss - cost2.ff;
			
			li cc = {0,0};
			li costs = s >= 0? st.get(st.head,0,MAXVAL,s,s) : cc;
			li coste = e <= MAXVAL-1?st.get(st.head,0,MAXVAL,e,e) : cc;
			li csts = {((ll)costs.ss*h[i] - costs.ff) + (coste.ff - (ll)h[i]*coste.ss), costs.ss + coste.ss};

			ll perThingycost = 0;
			ll offset = 0;
			ll prod = 0;
			if(csts.ss > 0){
				perThingycost = csts.ff / csts.ss;

			
				ll left = max((ll)0,(cost2.ff + cost1.ff) - b);
				prod = ceil(left*1.0/perThingycost);
				prod = min(prod,(ll)csts.ss);
				offset = prod*perThingycost;
			}	
			//cout << prod << " " << offset << " " << lo << " " << hi << endl;
			if(cost2.ff + cost1.ff - offset <= b){
				best = max(best,cost1.ss+cost2.ss - (int)prod);
				if(lo == hi)break;
				lo = mid+1;
			}else{
				if(lo == hi)break;
				hi = mid-1;
			}
		}
	}

	return best;
}

int ma1in(){
	int a[5] = {1,2,10,12,14};
	cout << besthub(5,50,a,6) << endl;
	return 0;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 117752 KB Output is correct
2 Correct 96 ms 117880 KB Output is correct
3 Correct 96 ms 117880 KB Output is correct
4 Correct 95 ms 117880 KB Output is correct
5 Correct 96 ms 117752 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 117796 KB Output is correct
2 Correct 96 ms 117880 KB Output is correct
3 Correct 95 ms 117756 KB Output is correct
4 Correct 97 ms 117672 KB Output is correct
5 Correct 97 ms 117784 KB Output is correct
6 Correct 97 ms 117752 KB Output is correct
7 Correct 97 ms 117752 KB Output is correct
8 Correct 97 ms 117752 KB Output is correct
9 Correct 96 ms 117740 KB Output is correct
10 Correct 96 ms 117748 KB Output is correct
11 Correct 96 ms 117788 KB Output is correct
12 Correct 96 ms 117752 KB Output is correct
13 Correct 96 ms 117672 KB Output is correct
14 Correct 96 ms 117752 KB Output is correct
15 Correct 97 ms 117664 KB Output is correct
16 Correct 97 ms 117668 KB Output is correct
17 Correct 96 ms 117752 KB Output is correct
18 Correct 96 ms 117732 KB Output is correct
19 Correct 97 ms 117752 KB Output is correct
20 Correct 113 ms 117724 KB Output is correct
21 Correct 101 ms 117852 KB Output is correct
22 Correct 101 ms 117884 KB Output is correct
23 Correct 103 ms 117752 KB Output is correct
24 Correct 102 ms 117752 KB Output is correct
25 Correct 103 ms 117752 KB Output is correct
26 Correct 103 ms 117752 KB Output is correct
27 Correct 103 ms 117752 KB Output is correct
28 Correct 105 ms 117880 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 117752 KB Output is correct
2 Correct 99 ms 117756 KB Output is correct
3 Correct 108 ms 117752 KB Output is correct
4 Correct 114 ms 117752 KB Output is correct
5 Correct 99 ms 117756 KB Output is correct
6 Correct 99 ms 117880 KB Output is correct
7 Correct 107 ms 117804 KB Output is correct
8 Correct 107 ms 117752 KB Output is correct
9 Correct 103 ms 117752 KB Output is correct
10 Correct 124 ms 117752 KB Output is correct
11 Correct 111 ms 117880 KB Output is correct
12 Correct 110 ms 117876 KB Output is correct
13 Correct 108 ms 117752 KB Output is correct
14 Correct 110 ms 117880 KB Output is correct
15 Correct 102 ms 117752 KB Output is correct
16 Correct 106 ms 117836 KB Output is correct
17 Correct 105 ms 117724 KB Output is correct
18 Correct 124 ms 117752 KB Output is correct
19 Correct 126 ms 117752 KB Output is correct
20 Correct 117 ms 117752 KB Output is correct
21 Correct 154 ms 117880 KB Output is correct
22 Correct 154 ms 117752 KB Output is correct
23 Correct 149 ms 117724 KB Output is correct
24 Correct 165 ms 117724 KB Output is correct
25 Correct 189 ms 117800 KB Output is correct
26 Correct 208 ms 117876 KB Output is correct
27 Correct 232 ms 117948 KB Output is correct
28 Correct 216 ms 117752 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 577 ms 118016 KB Output is correct
2 Correct 604 ms 117880 KB Output is correct
3 Execution timed out 1093 ms 119252 KB Time limit exceeded
4 Halted 0 ms 0 KB -