제출 #1183187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183187		dnnnda	Aliens (IOI16_aliens)	C++20	0 / 100	2095 ms	320 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
#define init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

struct Line{
    ll m, k, t;
    Line(){};
    Line(ll m, ll k, ll t): m(m), k(k), t(t){};
    ll operator()(const ll &x) const{
        return 1LL*m*x+k;
    }
};

pair<ll,ll> dp[100005]; // fee, -max_trans_time
ll l[100005], r[100005]={-1}, n, cov[100005];
deque<Line> dq;

bool over(Line L1, Line L2, ll val){
    return L1(val)>L2(val)||L1(val)==L2(val)&&abs(L1.t)<abs(L2.t);
}

bool del(Line L1, Line L2, Line L){
    return (L.k-L2.k)*(L1.m-L2.m)<=(L2.k-L1.k)*(L2.m-L.m);
}

pair<ll,ll> solve(ll p){
    auto ck=clock();
    dq.clear();
    for(int i=0 ; i<=n+1 ; i++) dp[i]={inff,0};
    dp[0]={0,0};
    dq.push_back(Line(-2*l[1],l[1]*l[1]-2*l[1]-cov[0]*cov[0],0));

    for(int i=1 ; i<=n ; i++){
        while(dq.size()>=2&&over(dq[0],dq[1],r[i])) dq.pop_front();
        dp[i]=min(dp[i],{dq[0](r[i])+(r[i]+1)*(r[i]+1)+p,dq[0].t-1});

        Line line(-2*l[i+1],dp[i].F+l[i+1]*l[i+1]-2*l[i+1]-cov[i]*cov[i],dp[i].S);
        while(dq.size()>=2&&del(dq.end()[-2],dq.end()[-1],line)) dq.pop_back();
        dq.push_back(line);
    }
    assert((double)(clock()-ck)/CLOCKS_PER_SEC<=0.1);
    return {dp[n].F,-dp[n].S};
}

ll take_photos(int N, int m, int K, vector<int> _r, vector<int> _c){
    vector<pair<int,int>> v, v2;
    for(int i=0 ; i<N ; i++){
        if(_r[i]>_c[i]) swap(_r[i],_c[i]);
        v.push_back({_r[i],_c[i]});
    }
    sort(v.begin(),v.end());
    for(int i=0 ; i<N ; i++){
        if(v2.empty()||v[i].S>v2.back().S) v2.push_back(v[i]);
    }
    n=v2.size();

    for(int i=0 ; i<n ; i++) l[i+1]=v2[i].F, r[i+1]=v2[i].S;
    for(int i=0 ; i<n ; i++) cov[i]=max(0LL,r[i]-l[i+1]+1);

    ll p=0;
    for(ll jump=1'000'000'000'000 ; jump ; jump>>=1){
        while(solve(p+jump).S>=K) p+=jump;
    }
    auto temp=solve(p);
    return temp.F-p*temp.S;
}

//#define LOCAL
#ifdef LOCAL
int main(){
    cout << take_photos(5,7,2,{0,4,4,4,4},{3,4,6,5,6}) << '\n';
    cout << take_photos(2,6,2,{1,4},{4,1}) << '\n';
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40