제출 #108355

#제출 시각아이디문제언어결과실행 시간메모리
108355rajarshi_basuAliens (IOI16_aliens)C++14
0 / 100
2 ms384 KiB
#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; dp[0][1] = 0; 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; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...