oj.uz

Submission #33786

# Submission time Handle Problem Language Result Execution time Memory
33786 2017-11-01T23:11:11 Z leejseo Aliens (IOI16_aliens) C++11
0 / 100
 0 ms 394212 KB 
#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long lld;
#define append push_back
#define MAXN 100001
#define all(v) (v).begin(), (v).end()

long long D[MAXN][501];

struct Point{
    int r, c;
} A[MAXN];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    // n : interesting place
    // m : row
    // k : max image
    vector <Point> arr;
    for (int i = 0; i < n; i ++) arr.append({min(r[i], c[i]), max(r[i], c[i])});
    sort(all(arr), [](const Point &a, const Point &b){
        if (a.c != b.c) return a.c < b.c;
        return a.r > b.r;
    });
    int K = min(k, n);
    for (int i=1; i <= n; i++) for(int j=1; j<=K; j++) D[i][j] = 1e18;
    for (int i=1; i<=n; i++) D[i][1] = (long long )(A[i].c - A[1].r+1 )*(A[i].c - A[1].r+1);
    for (int i=2; i<K; i++){
        for(int j=1; j<n; j++) for (int k=j+1; k<=n; k++){
            long long v = D[j][i] + (long long)(A[k].c - A[j+1].r+1)*(A[k].c - A[j+1].r+1);
            if (A[j+1].r <= A[j].c)
                v -= (long long)(A[j].c - A[j+1].r+1)*(A[k].c-A[j+1].r+1);
            D[k][i+1] = min(D[k][i+1], v);
        }
    }
    return D[n][K];
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 394212 KB Wrong answer: output = 1, expected = 4
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 394212 KB Correct answer: answer = 1
2 Incorrect 0 ms 394212 KB Wrong answer: output = 1, expected = 4
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 394212 KB Wrong answer: output = 1, expected = 4
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 394212 KB Wrong answer: output = 1, expected = 4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 394212 KB Wrong answer: output = 1, expected = 4
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 394212 KB Wrong answer: output = 1, expected = 4
2 Halted 0 ms 0 KB -