oj.uz

Submission #1104117

# Submission time Handle Problem Language Result Execution time Memory
1104117 2024-10-22T20:26:51 Z alexander707070 Aliens (IOI16_aliens) C++14
12 / 100
 11 ms 2676 KB 
#include<bits/stdc++.h>

#define MAXN 100007
using namespace std;

const long long inf=1e13,inff=1e18;

struct interval{
	int l,r;

	inline friend bool operator < (interval fr,interval sc){
		if(fr.l==sc.l)return fr.r>sc.r;
		return fr.l<sc.l;
	}
}s[MAXN],w[MAXN];

struct line{
	long long a,b,from;
	int cnt;

	long long val(long long x){
		return a*x+b;
	}
};

bool smaller(line fr,line sc,long long x){
	if(fr.val(x)<sc.val(x))return true;
	if(fr.val(x)==sc.val(x) and fr.cnt<sc.cnt)return true;
	return false;
}

long long intersec(line fr,line sc){
	long long x=(fr.b-sc.b)/(sc.a-fr.a);

	if(smaller(fr,sc,x+1))x++;
	if(!smaller(fr,sc,x))x--;

	return x;
}

struct CHT{

	deque<line> d;

	void init(){
		d.clear();
	}

	void addline(line s){
		while(!d.empty() and smaller(s,d.back(),d.back().from))d.pop_back();

		if(d.empty()){
			d.push_back({s.a,s.b,-inf,s.cnt});
		}else{
			d.push_back({s.a,s.b,intersec(s,d.back()),s.cnt});
		}
	}

	pair<long long,int> query(long long x){
		while(d.size()>1 and x>=d[1].from){
			d.pop_front();
		}

		return {d.front().val(x),d.front().cnt};
	}
}hull;

int n,m,k,sz;
long long bonus[MAXN];

long long dp[MAXN];
int cnt[MAXN];

long long coef(int id){
	return bonus[id] + dp[id-1] + w[id].l*(w[id].l-2); 
}

void solve(long long delta){
	hull.init();

	for(int i=1;i<=sz;i++){
		dp[i]=inff;

		for(int t=i;t>=1;t--){
			long long s=(long long) dp[t-1] + bonus[t] + w[i].r*(w[i].r+2) - 2*w[i].r*w[t].l + w[t].l*(w[t].l-2) + delta + 1;

			if(s<dp[i]){
				dp[i]=s; cnt[i]=cnt[t-1]+1;
			}else if(s==dp[i]){
				cnt[i]=min(cnt[i],cnt[t-1]+1);
			}
		}
		
		/*hull.addline({-2*w[i].l,coef(i),0,cnt[i-1]});
		pair<long long,int> curr=hull.query(w[i].r);

		dp[i]=curr.first+w[i].r*(w[i].r+2)+1; 
		cnt[i]=curr.second+1;*/
	}
}

long long bin(){
	long long l=-1,r=inf,tt;

	while(l+1<r){
		tt=(l+r)/2;

		solve(tt);

		if(cnt[sz]>k){
			l=tt;
		}else{
			r=tt;
		}
	}

	solve(r);
	if(cnt[sz]==k)return dp[sz]-cnt[sz]*r;
	
	long long val2=dp[sz]-cnt[sz]*r;
	int k2=cnt[sz];

	solve(r-1);
	long long val1=dp[sz]-cnt[sz]*(r-1);
	int k1=cnt[sz];

	return (long long) val1 + (k-k1)*(val2-val1)/(k2-k1);
}

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c){
	n=N; m=M; k=K;

	for(int i=1;i<=n;i++){
		s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
	}

	sort(s+1,s+n+1);

	for(int i=1;i<=n;i++){
		if(sz>0 and s[i].r<=w[sz].r)continue;
		sz++; w[sz]=s[i];
	}

	for(int i=1;i<=sz;i++){
		if(w[i-1].r>=w[i].l)bonus[i]=(w[i-1].r-w[i].l+1)*(w[i-1].r-w[i].l+1);
	}

	k=min(k,sz);

	return bin();
}

/*int main(){

	hull.init();
	cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";

	return 0;
}*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Correct answer: answer = 4
2 Correct 1 ms 2384 KB Correct answer: answer = 4
3 Correct 1 ms 2384 KB Correct answer: answer = 4
4 Incorrect 1 ms 2384 KB Wrong answer: output = 14, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Correct answer: answer = 1
2 Correct 1 ms 2384 KB Correct answer: answer = 4
3 Correct 1 ms 2384 KB Correct answer: answer = 1
4 Correct 1 ms 2384 KB Correct answer: answer = 5
5 Correct 1 ms 2384 KB Correct answer: answer = 41
6 Correct 1 ms 2384 KB Correct answer: answer = 71923
7 Correct 2 ms 2384 KB Correct answer: answer = 77137
8 Correct 8 ms 2384 KB Correct answer: answer = 764
9 Correct 11 ms 2384 KB Correct answer: answer = 250000
10 Correct 11 ms 2384 KB Correct answer: answer = 500
11 Correct 1 ms 2384 KB Correct answer: answer = 32
12 Correct 10 ms 2512 KB Correct answer: answer = 130050
13 Correct 11 ms 2384 KB Correct answer: answer = 5110
14 Correct 4 ms 2384 KB Correct answer: answer = 2626
15 Correct 4 ms 2676 KB Correct answer: answer = 796
16 Correct 11 ms 2384 KB Correct answer: answer = 7580
17 Correct 11 ms 2512 KB Correct answer: answer = 1904
18 Correct 7 ms 2384 KB Correct answer: answer = 996004
19 Correct 7 ms 2556 KB Correct answer: answer = 38817
20 Correct 7 ms 2384 KB Correct answer: answer = 4096
21 Correct 1 ms 2384 KB Correct answer: answer = 1
22 Correct 1 ms 2384 KB Correct answer: answer = 1
23 Correct 11 ms 2384 KB Correct answer: answer = 2040
24 Correct 1 ms 2384 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Correct answer: answer = 4
2 Correct 1 ms 2384 KB Correct answer: answer = 4
3 Correct 1 ms 2384 KB Correct answer: answer = 4
4 Incorrect 1 ms 2384 KB Wrong answer: output = 14, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Correct answer: answer = 4
2 Correct 1 ms 2384 KB Correct answer: answer = 4
3 Correct 1 ms 2384 KB Correct answer: answer = 4
4 Incorrect 1 ms 2384 KB Wrong answer: output = 14, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Correct answer: answer = 4
2 Correct 1 ms 2384 KB Correct answer: answer = 4
3 Correct 1 ms 2384 KB Correct answer: answer = 4
4 Incorrect 1 ms 2384 KB Wrong answer: output = 14, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Correct answer: answer = 4
2 Correct 1 ms 2384 KB Correct answer: answer = 4
3 Correct 1 ms 2384 KB Correct answer: answer = 4
4 Incorrect 1 ms 2384 KB Wrong answer: output = 14, expected = 12
5 Halted 0 ms 0 KB -