oj.uz

Submission #108354

# Submission time Handle Problem Language Result Execution time Memory
108354 2019-04-28T17:33:26 Z rajarshi_basu Aliens (IOI16_aliens) C++14
0 / 100
 3 ms 384 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 <complex>
#include <chrono>
#include <random>
#include <stack>
#include <set>
#include <fstream>

#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a; i <= b ; i++)
#define ss second
#define ff first
#define ll long long int
#define ii pair<ll,ll>
#define il pair<int,ll>
#define li pair<ll,int>
#define x ff
#define y ss
#define lii pair<ll,pair<int,int> > 
#define piil pair<int ,pair<int,int> > 
#define iii pair<pair<int,int>,int> 
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define mp make_pair

#include "aliens.h"

using namespace std;

const ll INF = 1e18;

vector<ii> all;

vector<ii> reduceList(vector<ii> v){
	sort(v.begin(), v.end());
	vector<ii> res;
	ll mx = 0;
	for(auto e:v){

		if(res.empty())res.pb(e);
		else if(res.back().ff < e.ff){
			if(e.ss > mx)res.pb(e);
		}else{
			res.back() = e;
		}
		mx = max(mx,e.ss);
	}
	return res;
}

vector<ii> createRanges(vi r,vi c,int n){
	vector<ii> all;
	FOR(i,n)all.pb({min(r[i],c[i]),max(r[i],c[i])});
	return all;
}

ll cost(int t,int i){
	i--;
	//cout << "afsf " << i << " " << all.size() <<  endl;
	ll t1 = all[i].ss - all[t].ff + 1; t1*=t1;
	ll t2 = max((ll)0,(t-1 <0)?0:(all[t-1].ss-all[t].ff+1)); t2 *= t2;
	//cout << t1 << " " << t2 << endl;
	//cout << t1-t2 << endl;
	return t1 - t2;
}

ll dp[50*100+1][2];
int opt[50*100+1][2];

void computeDp(int k){
	
	int n = all.size();
	k = min(n,k);
	//cout << n << " " << k << endl;
	
	FOR(i,n+1)dp[i][0] = INF;
	dp[0][0] = 0;
	//FOR(i,n+1)dp[0][i]= 0;

	FOR(j,k+1){
		if(j == 0)continue;
		for(int i = n;i>=1;i--){
			ll opti = INF;
			int ind = 1;
			FORE(t,max(opt[i][0],1),(i==n?n:opt[i+1][1])){
				if(opti > dp[t-1][0] + cost(t-1,i)){
					opti = dp[t-1][0] + cost(t-1,i);
					ind = t;
				}
				//opti = min(opt,dp[t-1][j-1] + cost(t-1,i));
			}
			opt[i][1] = ind;
			dp[i][1] = opti;
		}
		FOR(i,n)dp[i][0] = dp[i][1],opt[i][0]= opt[i][1];
	}
}

ll take_photos(int n,int m,int k,vi r,vi c){
	all = reduceList(createRanges(r,c,n));
	//for(auto e:all)cout << e.ff<< ";"<<e.ss << endl;
	computeDp(k);/*
	FOR(i,min((int)all.size(),k)+1){
	FOR(j,all.size()+1){
		cout << dp[i][j] << " ";
	};cout << endl;}*/
	return dp[all.size()][min((int)all.size(),k)];
	//return 0;
}


/*
int main(){
	//int a[2] = {2,4,4,4,4};
	//int b[2] = {3,5,6,5,6};
	vi a;
	vi b;
	a.pb(1);a.pb(4);
	b.pb(6);b.pb(7);
	cout << take_photos(2,7,2,a,b) << endl;
	return 0;
}
*/

Subtask #1
0 / 4.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 40.0

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