# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
982435 | 2024-05-14T08:58:14 Z | totoro | Aliens (IOI16_aliens) | C++17 | 96 ms | 2336 KB |
// UNSOLVED SUBTASK 1 (04 pts) // UNSOLVED SUBTASK 2 (12 pts) // UNSOLVED SUBTASK 3 (09 pts) // UNSOLVED SUBTASK 4 (16 pts) // UNSOLVED SUBTASK 5 (19 pts) // UNSOLVED SUBTASK 6 (40 pts) // [+-+]---------------------- // TOTAL 0/100 pts #include "aliens.h" #include <algorithm> #include <climits> #include <vector> struct Coordinate { long long row, col; Coordinate(long long row, long long col) : row(std::min(row, col)), col(std::max(row, col)) {} bool operator<(const Coordinate& other) const { if (row == other.row) { return col > other.col; } return row < other.row; } }; struct Range { long long start, end; Range(long long start, long long end) : start(start), end(end){}; long long merge(const Range& other) const { return 2 * (other.start - start) * (other.end - end) - (other.start > end ? (other.start - end - 1) * (other.start - end - 1) : 0); } }; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { std::vector<Coordinate> points; for (size_t i = 0; i < n; ++i) { points.push_back(Coordinate(r[i], c[i])); } std::sort(points.begin(), points.end()); std::vector<Range> ranges; long long furthestStart = -1; long long furthestEnd = -1; for (size_t i = 0; i < points.size(); ++i) { Coordinate point = points[i]; if (point.row > furthestStart && point.col > furthestEnd) { ranges.emplace_back(point.row, point.col); furthestStart = point.row; furthestEnd = point.col; } } std::vector<std::vector<long long>> dp; for (size_t range = 0; range < ranges.size(); ++range) { dp.emplace_back(); for (size_t coverCount = 1; coverCount <= k; ++coverCount) { if (coverCount == 1 || range == 0) { dp[range].push_back((ranges[range].end - ranges[0].start + 1) * (ranges[range].end - ranges[0].start + 1)); continue; } long long best = LLONG_MAX; for (size_t earlier = 0; earlier < range; ++earlier) { long long score = dp[earlier][coverCount - 2] + (ranges[range].end - ranges[earlier + 1].start + 1) * (ranges[range].end - ranges[earlier + 1].start + 1); if (ranges[range].start <= ranges[earlier].end) { score -= (ranges[earlier].end - ranges[range].start + 1) * (ranges[earlier].end - ranges[range].start + 1); } if (score < best) { best = score; } } dp[range].push_back(best); } } return dp[ranges.size() - 1][k - 1]; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 348 KB | Correct answer: answer = 12 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 52 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 348 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 348 KB | Correct answer: answer = 7696 |
9 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
10 | Correct | 0 ms | 348 KB | Correct answer: answer = 2374 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 348 KB | Correct answer: answer = 49 |
13 | Correct | 0 ms | 348 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 348 KB | Correct answer: answer = 7550 |
15 | Correct | 0 ms | 348 KB | Correct answer: answer = 7220 |
16 | Correct | 1 ms | 344 KB | Correct answer: answer = 7550 |
17 | Correct | 1 ms | 512 KB | Correct answer: answer = 10000 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 348 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Correct answer: answer = 1 |
2 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
4 | Correct | 0 ms | 348 KB | Correct answer: answer = 5 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 41 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 71923 |
7 | Correct | 1 ms | 420 KB | Correct answer: answer = 77137 |
8 | Correct | 29 ms | 1104 KB | Correct answer: answer = 764 |
9 | Correct | 1 ms | 348 KB | Correct answer: answer = 250000 |
10 | Correct | 96 ms | 2336 KB | Correct answer: answer = 500 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 32 |
12 | Correct | 1 ms | 348 KB | Correct answer: answer = 130050 |
13 | Correct | 9 ms | 604 KB | Correct answer: answer = 5110 |
14 | Correct | 2 ms | 348 KB | Correct answer: answer = 2626 |
15 | Correct | 4 ms | 600 KB | Correct answer: answer = 796 |
16 | Correct | 6 ms | 600 KB | Correct answer: answer = 7580 |
17 | Correct | 24 ms | 1360 KB | Correct answer: answer = 1904 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 996004 |
19 | Correct | 3 ms | 348 KB | Correct answer: answer = 38817 |
20 | Correct | 11 ms | 700 KB | Correct answer: answer = 4096 |
21 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
22 | Correct | 0 ms | 348 KB | Correct answer: answer = 1 |
23 | Correct | 22 ms | 860 KB | Correct answer: answer = 2040 |
24 | Correct | 1 ms | 348 KB | Correct answer: answer = 2 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 348 KB | Correct answer: answer = 12 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 52 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 348 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 348 KB | Correct answer: answer = 7696 |
9 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
10 | Correct | 0 ms | 348 KB | Correct answer: answer = 2374 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 348 KB | Correct answer: answer = 49 |
13 | Correct | 0 ms | 348 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 348 KB | Correct answer: answer = 7550 |
15 | Correct | 0 ms | 348 KB | Correct answer: answer = 7220 |
16 | Correct | 1 ms | 344 KB | Correct answer: answer = 7550 |
17 | Correct | 1 ms | 512 KB | Correct answer: answer = 10000 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 348 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
21 | Correct | 1 ms | 344 KB | Correct answer: answer = 1 |
22 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
23 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
24 | Correct | 0 ms | 348 KB | Correct answer: answer = 5 |
25 | Correct | 0 ms | 348 KB | Correct answer: answer = 41 |
26 | Correct | 0 ms | 348 KB | Correct answer: answer = 71923 |
27 | Correct | 1 ms | 420 KB | Correct answer: answer = 77137 |
28 | Correct | 29 ms | 1104 KB | Correct answer: answer = 764 |
29 | Correct | 1 ms | 348 KB | Correct answer: answer = 250000 |
30 | Correct | 96 ms | 2336 KB | Correct answer: answer = 500 |
31 | Correct | 0 ms | 348 KB | Correct answer: answer = 32 |
32 | Correct | 1 ms | 348 KB | Correct answer: answer = 130050 |
33 | Correct | 9 ms | 604 KB | Correct answer: answer = 5110 |
34 | Correct | 2 ms | 348 KB | Correct answer: answer = 2626 |
35 | Correct | 4 ms | 600 KB | Correct answer: answer = 796 |
36 | Correct | 6 ms | 600 KB | Correct answer: answer = 7580 |
37 | Correct | 24 ms | 1360 KB | Correct answer: answer = 1904 |
38 | Correct | 1 ms | 348 KB | Correct answer: answer = 996004 |
39 | Correct | 3 ms | 348 KB | Correct answer: answer = 38817 |
40 | Correct | 11 ms | 700 KB | Correct answer: answer = 4096 |
41 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
42 | Correct | 0 ms | 348 KB | Correct answer: answer = 1 |
43 | Correct | 22 ms | 860 KB | Correct answer: answer = 2040 |
44 | Correct | 1 ms | 348 KB | Correct answer: answer = 2 |
45 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
46 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
47 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
48 | Correct | 0 ms | 344 KB | Correct answer: answer = 21 |
49 | Incorrect | 0 ms | 344 KB | Wrong answer: output = 73, expected = 71 |
50 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 348 KB | Correct answer: answer = 12 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 52 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 348 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 348 KB | Correct answer: answer = 7696 |
9 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
10 | Correct | 0 ms | 348 KB | Correct answer: answer = 2374 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 348 KB | Correct answer: answer = 49 |
13 | Correct | 0 ms | 348 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 348 KB | Correct answer: answer = 7550 |
15 | Correct | 0 ms | 348 KB | Correct answer: answer = 7220 |
16 | Correct | 1 ms | 344 KB | Correct answer: answer = 7550 |
17 | Correct | 1 ms | 512 KB | Correct answer: answer = 10000 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 348 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
21 | Correct | 1 ms | 344 KB | Correct answer: answer = 1 |
22 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
23 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
24 | Correct | 0 ms | 348 KB | Correct answer: answer = 5 |
25 | Correct | 0 ms | 348 KB | Correct answer: answer = 41 |
26 | Correct | 0 ms | 348 KB | Correct answer: answer = 71923 |
27 | Correct | 1 ms | 420 KB | Correct answer: answer = 77137 |
28 | Correct | 29 ms | 1104 KB | Correct answer: answer = 764 |
29 | Correct | 1 ms | 348 KB | Correct answer: answer = 250000 |
30 | Correct | 96 ms | 2336 KB | Correct answer: answer = 500 |
31 | Correct | 0 ms | 348 KB | Correct answer: answer = 32 |
32 | Correct | 1 ms | 348 KB | Correct answer: answer = 130050 |
33 | Correct | 9 ms | 604 KB | Correct answer: answer = 5110 |
34 | Correct | 2 ms | 348 KB | Correct answer: answer = 2626 |
35 | Correct | 4 ms | 600 KB | Correct answer: answer = 796 |
36 | Correct | 6 ms | 600 KB | Correct answer: answer = 7580 |
37 | Correct | 24 ms | 1360 KB | Correct answer: answer = 1904 |
38 | Correct | 1 ms | 348 KB | Correct answer: answer = 996004 |
39 | Correct | 3 ms | 348 KB | Correct answer: answer = 38817 |
40 | Correct | 11 ms | 700 KB | Correct answer: answer = 4096 |
41 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
42 | Correct | 0 ms | 348 KB | Correct answer: answer = 1 |
43 | Correct | 22 ms | 860 KB | Correct answer: answer = 2040 |
44 | Correct | 1 ms | 348 KB | Correct answer: answer = 2 |
45 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
46 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
47 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
48 | Correct | 0 ms | 344 KB | Correct answer: answer = 21 |
49 | Incorrect | 0 ms | 344 KB | Wrong answer: output = 73, expected = 71 |
50 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 348 KB | Correct answer: answer = 12 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 52 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 348 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 348 KB | Correct answer: answer = 7696 |
9 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
10 | Correct | 0 ms | 348 KB | Correct answer: answer = 2374 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 348 KB | Correct answer: answer = 49 |
13 | Correct | 0 ms | 348 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 348 KB | Correct answer: answer = 7550 |
15 | Correct | 0 ms | 348 KB | Correct answer: answer = 7220 |
16 | Correct | 1 ms | 344 KB | Correct answer: answer = 7550 |
17 | Correct | 1 ms | 512 KB | Correct answer: answer = 10000 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 348 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
21 | Correct | 1 ms | 344 KB | Correct answer: answer = 1 |
22 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
23 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
24 | Correct | 0 ms | 348 KB | Correct answer: answer = 5 |
25 | Correct | 0 ms | 348 KB | Correct answer: answer = 41 |
26 | Correct | 0 ms | 348 KB | Correct answer: answer = 71923 |
27 | Correct | 1 ms | 420 KB | Correct answer: answer = 77137 |
28 | Correct | 29 ms | 1104 KB | Correct answer: answer = 764 |
29 | Correct | 1 ms | 348 KB | Correct answer: answer = 250000 |
30 | Correct | 96 ms | 2336 KB | Correct answer: answer = 500 |
31 | Correct | 0 ms | 348 KB | Correct answer: answer = 32 |
32 | Correct | 1 ms | 348 KB | Correct answer: answer = 130050 |
33 | Correct | 9 ms | 604 KB | Correct answer: answer = 5110 |
34 | Correct | 2 ms | 348 KB | Correct answer: answer = 2626 |
35 | Correct | 4 ms | 600 KB | Correct answer: answer = 796 |
36 | Correct | 6 ms | 600 KB | Correct answer: answer = 7580 |
37 | Correct | 24 ms | 1360 KB | Correct answer: answer = 1904 |
38 | Correct | 1 ms | 348 KB | Correct answer: answer = 996004 |
39 | Correct | 3 ms | 348 KB | Correct answer: answer = 38817 |
40 | Correct | 11 ms | 700 KB | Correct answer: answer = 4096 |
41 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
42 | Correct | 0 ms | 348 KB | Correct answer: answer = 1 |
43 | Correct | 22 ms | 860 KB | Correct answer: answer = 2040 |
44 | Correct | 1 ms | 348 KB | Correct answer: answer = 2 |
45 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
46 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
47 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
48 | Correct | 0 ms | 344 KB | Correct answer: answer = 21 |
49 | Incorrect | 0 ms | 344 KB | Wrong answer: output = 73, expected = 71 |
50 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 348 KB | Correct answer: answer = 12 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 52 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 348 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 348 KB | Correct answer: answer = 7696 |
9 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
10 | Correct | 0 ms | 348 KB | Correct answer: answer = 2374 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 348 KB | Correct answer: answer = 49 |
13 | Correct | 0 ms | 348 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 348 KB | Correct answer: answer = 7550 |
15 | Correct | 0 ms | 348 KB | Correct answer: answer = 7220 |
16 | Correct | 1 ms | 344 KB | Correct answer: answer = 7550 |
17 | Correct | 1 ms | 512 KB | Correct answer: answer = 10000 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 348 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 348 KB | Correct answer: answer = 10000 |
21 | Correct | 1 ms | 344 KB | Correct answer: answer = 1 |
22 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
23 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
24 | Correct | 0 ms | 348 KB | Correct answer: answer = 5 |
25 | Correct | 0 ms | 348 KB | Correct answer: answer = 41 |
26 | Correct | 0 ms | 348 KB | Correct answer: answer = 71923 |
27 | Correct | 1 ms | 420 KB | Correct answer: answer = 77137 |
28 | Correct | 29 ms | 1104 KB | Correct answer: answer = 764 |
29 | Correct | 1 ms | 348 KB | Correct answer: answer = 250000 |
30 | Correct | 96 ms | 2336 KB | Correct answer: answer = 500 |
31 | Correct | 0 ms | 348 KB | Correct answer: answer = 32 |
32 | Correct | 1 ms | 348 KB | Correct answer: answer = 130050 |
33 | Correct | 9 ms | 604 KB | Correct answer: answer = 5110 |
34 | Correct | 2 ms | 348 KB | Correct answer: answer = 2626 |
35 | Correct | 4 ms | 600 KB | Correct answer: answer = 796 |
36 | Correct | 6 ms | 600 KB | Correct answer: answer = 7580 |
37 | Correct | 24 ms | 1360 KB | Correct answer: answer = 1904 |
38 | Correct | 1 ms | 348 KB | Correct answer: answer = 996004 |
39 | Correct | 3 ms | 348 KB | Correct answer: answer = 38817 |
40 | Correct | 11 ms | 700 KB | Correct answer: answer = 4096 |
41 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
42 | Correct | 0 ms | 348 KB | Correct answer: answer = 1 |
43 | Correct | 22 ms | 860 KB | Correct answer: answer = 2040 |
44 | Correct | 1 ms | 348 KB | Correct answer: answer = 2 |
45 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
46 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
47 | Correct | 0 ms | 348 KB | Correct answer: answer = 9 |
48 | Correct | 0 ms | 344 KB | Correct answer: answer = 21 |
49 | Incorrect | 0 ms | 344 KB | Wrong answer: output = 73, expected = 71 |
50 | Halted | 0 ms | 0 KB | - |