Submission #197405

#	Time	Username	Problem	Language	Result	Execution time	Memory
197405		abacaba	Aliens (IOI16_aliens)	C++14	0 / 100	4 ms	2428 KiB

aliens

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm> 
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int mod = 1e9 + 7;
const ll inf = 2e15;
const int N = 5e2 + 15;
ll dp[N][N];
int l[N], r[N];
int ord[N];
vector <int> tmp;

inline ll sq(ll x) {
    return x * x;
}

inline void Min(ll &a, ll b) {
    a = min(a, b);
}

ll take_photos(int n, int m, int k, std::vector<int> row, std::vector<int> col) {
    for(int i = 0; i < n; ++i) {
        l[i+1] = min(row[i], col[i]) + 1;
        r[i+1] = max(row[i], col[i]) + 1;
        ord[i+1] = i+1;
    }
    sort(ord + 1, ord + 1 + n, [&](int x, int y) {
        return mp(l[x], -r[x]) < mp(l[y], -r[y]);
    });
    for(int i = 1; i <= n; ++i)
        if(tmp.empty() || !(l[tmp.back()] <= l[ord[i]] && r[tmp.back()] >= r[ord[i]]))
            tmp.pb(ord[i]);
    n = tmp.size();
    for(int i = 1; i <= n; ++i)
        l[i] = l[tmp[i-1]], r[i] = r[tmp[i-1]];
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            dp[i][j] = inf;
    dp[0][0] = 0;
    for(int t = 1; t <= k; ++t)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= i; ++j)
                Min(dp[i][t], dp[j-1][t-1] + sq(r[i] - l[j] + 1) - sq(max(0, r[j-1] - l[j] + 1)));
    return *min_element(dp[n] + 1, dp[n] + 1 + k);
}

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