Submission #1222256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222256		pravcoder	Aliens (IOI16_aliens)	C++20	4 / 100	0 ms	328 KiB

aliens

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

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define vec vector
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vec<int> vi;
typedef vec<vi> v2i;
typedef pair<int, int> pi;
typedef vec<pi> vpi;
typedef vec<bool> vb;
typedef vec<ll> vl;
typedef vec<vl> v2l;

ll s1(int n, int m, vi& r, vi& c) {
    ll ans = 0;
    v2i g(m, vi(m, 0));
    rep(i, n) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        rept(y, r[i], c[i]+1) {
            rept(x, r[i], c[i]+1) {
                if (g[y][x] == 0) ans++;
                g[y][x] = 1;
            }
        }
    }
    return ans;
}

ll s2(int n, int m, int k, vi& r) {
    r.pb(-1);
    sort(all(r));
    v2l dp(r.size(), vl(k+1, 0));
    rept(i, 1, n+1) {
        rept(c, 1, k+1) {
            dp[i][c] = dp[i-1][k-1] + 1;
            rept(j, 1, i) {
                dp[i][c] = min(dp[i][c], dp[i-j-1][k-1] + (r[i]-r[i-j]+1)*(r[i]-r[i-j]+1));
            }
        }
    }
    return dp[n][k];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    if (n==k) return s1(n, m, r, c);
    return s2(n, m, k, r);
}

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: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40