Submission #1211780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211780		sano	Aliens (IOI16_aliens)	C++20	25 / 100	2097 ms	63048 KiB

aliens

#include "aliens.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vec<vec<int>> dp(m+1, vec<int>(k+1, NEK));
    vec<int> pr(m, -1), ps(m, 0);
    For(i, n) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        pr[r[i]] = max(pr[r[i]], c[i]);
        ps[c[i]]++;
    }
    For(i, k+1) dp[m][i] = 0;
    int pos = 0;
    rfor(i, m - 1) {
        pos = i;
        if (ps[i] == 0) For(j, k+1) dp[i][j] = 0;
        else break;
    }
    ffor(j, 1, k+1) {
        rfor(i, pos) {
            int som = -1;
            For(l, m) {
                if (pr[l] >= i) {
                    som = l;
                    break;
                }
            }
            for (int l = pr[som]; l < m; l++) {
                //berieme az po stlpec l, teda stvorec velkosti l - som + 1
                dp[i][j] = min(dp[i][j], dp[l+1][j - 1] + (l - som + 1) * (l - som + 1) - max(0, (i - som)) * max(0, (i - som)));
            }
        }
    }
    return dp[0][k];
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k; cin >> n >> m >> k;
    vec<int> r(n), c(n);
    For(i, n) {
        cin >> r[i] >> c[i];
    }
    cout << take_photos(n, m, k, r, c) << '\n';
    return 0;
}*/

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