Submission #1272497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272497		kl0989e	Aliens (IOI16_aliens)	C++20	0 / 100	1 ms	344 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

struct cht {
    vector<pl> stk;
    int pt=0;

    void add(ll a, ll b) {
        stk.pb({a,b});
    }

    ll get(ll x) {
        while (pt<stk.size()-1 && (x*stk[pt].fi+stk[pt].se)>=(x*stk[pt+1].fi+stk[pt+1].se)) {
            pt++;
        }
        return x*stk[pt].fi+stk[pt].se;
    }
};

long long take_photos(int n, int m, int k, vi r, vi c) {
    vector<pl> tpo(n);
    vl pmx(n);
    for (int i=0; i<n; i++) {
        tpo[i].fi=min(r[i],c[i]);
        tpo[i].se=max(r[i],c[i]);
    }
    sort(all(tpo));
    vector<pl> po={tpo[0]};
    for (int i=0; i<n; i++) {
        if (po.back().fi==tpo[i].fi) {
            po.back().se=tpo[i].se;
        }
        if (po.back().se<tpo[i].se) {
            po.pb(tpo[i]);
        }
    }
    n=po.size();
    vector<cht> chts(k+1);
    for (int i=0; i<k; i++) {
        chts[i].add(2*(1-po[0].fi),(1-po[0].fi)*(1-po[0].fi));
    }
    vector<vl> dp(n+1,vl(k+1,1e13));
    dp[0][0]=0;
    for (int i=1; i<=n; i++) {
        for (int j=k; j>=1; j--) {
            dp[i][j]=min(dp[i][j],po[i-1].se*po[i-1].se+chts[j-1].get(po[i-1].se));
            ll sub=0;
            if (n>i+1 && po[i].se>=po[i+1].fi) {
                sub=(po[i].se-po[i+1].fi+1)*(po[i].se-po[i+1].fi+1);
            }
            chts[j].add(2*(1-po[i].fi),dp[i][j]-sub+(1-po[i].fi)*(1-po[i].fi));
            /*
            ll mx=po[i-1].se;
            for (int i2=i-1; i2>=0; i2--) {
                ll sub=0;
                if (i2>0 && po[i2-1].se>=po[i2].fi) {
                    sub=(po[i2-1].se-po[i2].fi+1)*(po[i2-1].se-po[i2].fi+1);
                }
                dp[i][j]=min(dp[i][j],dp[i2][j-1]+(mx-po[i2].fi+1)*(mx-po[i2].fi+1)-sub);
                // b = dp[i2][j-1]-sub+(1-po[i2].fi)*(1-po[i2].fi)
                // a = 2(1-po[i2].fi)
            }*/
        }
    }
    return *min_element(all(dp[n]));
}

Compilation message (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