Submission #731600

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
731600	2023-04-27 16:02:59	jasen_penchev	Aliens (IOI16_aliens)	C++14	41 / 100	714 ms	512876 KiB

aliens

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/// Divide and Conquer Optimization
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#define endl '\n'
using namespace std;
const int MAXN = 4000;
long long dp[MAXN + 5][MAXN + 5];
long long cost[MAXN + 5][MAXN + 5];
void calc(int k, int from, int to, int mn, int mx)
{
    int mid = (from + to) / 2;
    int opt = -1;
    dp[mid][k] = (long long)(1e18);
    for (int i = max(k - 1, mn); i <= min(mid - 1, mx); ++ i)
    {
        if (dp[mid][k] > dp[i][k - 1] + cost[i + 1][mid])
        {
            dp[mid][k] = dp[i][k - 1] + cost[i + 1][mid];
            opt = i;
        }
    }
    if (from == to) return;
    if (from <= mid - 1) calc(k, from, mid - 1, mn, opt);
    if (mid + 1 <= to) calc(k, mid + 1, to, opt, mx);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for (auto [r, l] : temp)
      |               ^

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