| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1214351 | thdh__ | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
/*
Competitive Programming notes that I need to study & fix my dumbass self:
1. Coding:
- Always be sure to check the memory of arrays (maybe use vectors), for loops, I don't know
- Always try to maximize the memory if possible, even if you are going for subtasks
- Do not exploit #define int long long, it will kill you
2. Stress:
- Don't be cocky and think stressing with your dumbass brute-force solution will give you guaranteed AC.
- Always try generating big testcases and try if they run
3. Time management:
- Don't overcommit or undercommit, always spend a certain amount of time to think a problem, don't just look at it and say I'm fucked
- Do not spend too much time coding brute-force solutions, they should be easily-codable solutions that don't take up too much time
I hate offline because I am dumb
*/
typedef pair<ll, ll> ii;
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;}
struct Line {
ll m, b;
ll x;
int cnt;
};
struct CHT {
deque<Line> dq;
static ll divCeil(ll a, ll b) {
if (a >= 0) return (a + b - 1) / b;
else return a / b;
}
static ll intersect(const Line &l1, const Line &l2) {
return divCeil(l2.b - l1.b, l1.m - l2.m);
}
void addLine(ll m, ll b, int cnt) {
Line nw{m, b, 0, cnt};
while (!dq.empty()) {
nw.x = intersect(dq.back(), nw);
if (nw.x <= dq.back().x) dq.pop_back();
else break;
}
if (dq.empty()) {
nw.x = LLONG_MIN;
}
dq.push_back(nw);
}
pair<ll,int> query(ll x) {
while (dq.size() >= 2 && dq[1].x <= x) {
dq.pop_front();
}
auto &L = dq.front();
return {L.m * x + L.b, L.cnt};
}
};
bool cmp(ii x, ii y)
{
return x.fi == y.fi ? x.se > y.se : x.fi < y.fi;
}
vector<ll> l,r;
ii calc(int lb)
{
int n = l.size()-1;
vector<ii> dp(n+1, {0, 0});
CHT cht;
for (int i = 1; i <= n; i++)
{
// cout<<2 * (l[i]-1)<<" "<<dp[i-1].fi + (l[i]-1) * (l[i]-1) - max(0ll, r[i-1] - (l[i]-1)) * max(0ll, r[i-1] - (l[i]-1))<<endl;
cht.addLine(2 * (l[i]-1), dp[i-1].fi + (l[i]-1) * (l[i]-1) - max(0ll, r[i-1] - (l[i]-1)) * max(0ll, r[i-1] - (l[i]-1)), dp[i-1].se);
ii tmp = cht.query(-r[i]);
// cout<<tmp.fi<<endl;
dp[i].fi = tmp.fi + r[i] * r[i] + lb;
dp[i].se = tmp.se + 1;
}
// cout<<dp[n].fi - lb<<" "<<dp[n].se<<endl;
return dp[n];
}
ll take_photos(int n, int m, int k, vector<int> rr, vector<int> cc)
{
vector<ii> a;
for (int i = 0; i < n; i++) a.pb({min(rr[i], cc[i]), max(rr[i], cc[i])});
sort(all(a), cmp);
// for (auto i : a) cout<<i.fi<<" "<<i.se<<endl;
int mx = 0;
l.pb(-1), r.pb(-1);
for (int i = 0; i < n; i++)
{
if (mx >= a[i].se) continue;
mx = max(mx, a[i].se);
l.pb(a[i].fi), r.pb(a[i].se);
}
// for (int i = 0; i < l.size(); i++) cout<<l[i]<<" "<<r[i]<<endl;
ll l1 = 0, r1 = 1e18;
array<ll, 3> ans = {0, 0, 0};
while (l1 <= r1)
{
ll mid = l1+r1>>1;
ii tmp = calc(mid);
if (tmp.se <= k) l1 = mid+1, ans = {tmp.fi, mid, tmp.se};
else r1 = mid-1;
}
return ans[0] - ans[1] * ans[2];
}
// void solve()
// {
// int n,m,k;
// cin>>n>>m>>k;
// vector<int> rr(n), cc(n);
// for (int i = 0; i < n; i++) cin>>rr[i];
// for (int i = 0; i < n; i++) cin>>cc[i];
// cout<<take_photos(n,m,k,rr,cc);
// }
/*
Go through the mistakes you usually make and revise your code, for god's sake...
*/
// signed main()
// {
// bruh
// //freopen("input.inp","r",stdin);
// //freopen("output.inp","w",stdout);
// int t = 1;
// // cin>>t;
// while (t--)
// {
// solve();
// cout<<"\n";
// }
// }