oj.uz

답안 #393070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393070 2021-04-22T16:20:52 Z Tc14 Aliens (IOI16_aliens) C++17
12 / 100
 39 ms 2316 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;

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

ll take_photos(int n, int m, int k, ve<int> R, ve<int> C) {

    map<int, int> M;
    ve<pii> P;

    for (int i = 0; i < n; i++) {
        int r = R[i];
        int c = C[i];
        if (c < r) swap(r, c);
        if (M.find(r) == M.end()) M[r] = c;
        else M[r] = max(M[r], c);
    }

    int cOld = -1;
    n = 0;
    for (pii p : M) {
        int r, c;
        tie(r, c) = p;
        if (c > cOld) {
            cOld = c;
            P.push_back({r, c});
            n++;
        }
    }

    ve<ll> L(n);
    for (int i = 1; i < n; i++) {
        if (P[i - 1].second >= P[i].first) {
            L[1] = sq(P[i - 1].second - P[i].first + 1);
        }
    }

    ve<ve<ll>> DP(k + 1, ve<ll>(n));
    for (int i = 0; i < n; i++) {
        DP[1][i] = sq(P[i].second - P[0].first + 1);
    }

    for (int i = 2; i <= k; i++) {
        for (int j = i - 1; j < n; j++) {

            DP[i][j] = LLINF;

            for (int l = i - 1; l <= j; l++) {

                ll v = DP[i - 1][l - 1];
                v += sq(P[j].second - P[l].first + 1);
                v -= L[l];

                DP[i][j] = min(DP[i][j], v);
            }
        }

    }

    return DP[min(k, n)][n - 1];
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 208 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Incorrect 1 ms 296 KB Wrong answer: output = 68, expected = 52
6 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 1
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 1
4 Correct 1 ms 204 KB Correct answer: answer = 5
5 Correct 1 ms 204 KB Correct answer: answer = 41
6 Correct 1 ms 204 KB Correct answer: answer = 71923
7 Correct 1 ms 332 KB Correct answer: answer = 77137
8 Correct 23 ms 1100 KB Correct answer: answer = 764
9 Correct 1 ms 332 KB Correct answer: answer = 250000
10 Correct 39 ms 2316 KB Correct answer: answer = 500
11 Correct 1 ms 204 KB Correct answer: answer = 32
12 Correct 1 ms 332 KB Correct answer: answer = 130050
13 Correct 13 ms 460 KB Correct answer: answer = 5110
14 Correct 3 ms 296 KB Correct answer: answer = 2626
15 Correct 5 ms 460 KB Correct answer: answer = 796
16 Correct 7 ms 472 KB Correct answer: answer = 7580
17 Correct 23 ms 848 KB Correct answer: answer = 1904
18 Correct 1 ms 296 KB Correct answer: answer = 996004
19 Correct 3 ms 332 KB Correct answer: answer = 38817
20 Correct 14 ms 588 KB Correct answer: answer = 4096
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 332 KB Correct answer: answer = 1
23 Correct 22 ms 832 KB Correct answer: answer = 2040
24 Correct 1 ms 304 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 208 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Incorrect 1 ms 296 KB Wrong answer: output = 68, expected = 52
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 208 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Incorrect 1 ms 296 KB Wrong answer: output = 68, expected = 52
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 208 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Incorrect 1 ms 296 KB Wrong answer: output = 68, expected = 52
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 208 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Incorrect 1 ms 296 KB Wrong answer: output = 68, expected = 52
6 Halted 0 ms 0 KB -