oj.uz

Submission #288546

# Submission time Handle Problem Language Result Execution time Memory
288546 2020-09-01T15:47:21 Z arayi Aliens (IOI16_aliens) C++17
0 / 100
 1 ms 768 KB 
#include <bits/stdc++.h>
#include "aliens.h"
#define lli long long int
using namespace std;

const int N = 1111;

lli dp[N][N], mx[N];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    for (int i = 0; i < n; i++)
    {
        mx[max(r[i], c[i]) + 1] = max(abs(r[i] - c[i]) + 1LL, mx[max(r[i], c[i]) + 1]);
    }
    for (int i = 1; i <= m; i++)
    {
        dp[i][0] = m * m;
        for (int j = 1; j <= k; j++)
        {
            lli mxx = mx[i];
            dp[i][j] = i * i;
            int i1 = i;
            while(i1 > 0)
            {
                while(i1 > 1 && mx[i1 - 1] + i - i1 + 1 < mxx) i1--;
                i1--;
                dp[i][j] = min(dp[i][j], dp[i1][j - 1] + mxx * mxx - max(0LL, (mxx - i + i1)) * max(0LL, (mxx - i + i1)));
                mxx = mx[i1] + i - i1;
            }
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
    }
    return dp[m][k];
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 384 KB Correct answer: answer = 4
3 Correct 0 ms 384 KB Correct answer: answer = 4
4 Correct 1 ms 384 KB Correct answer: answer = 12
5 Correct 0 ms 384 KB Correct answer: answer = 52
6 Correct 1 ms 384 KB Correct answer: answer = 210
7 Correct 0 ms 384 KB Correct answer: answer = 88
8 Incorrect 1 ms 768 KB Wrong answer: output = 7698, expected = 7696
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 384 KB Correct answer: answer = 4
3 Correct 0 ms 384 KB Correct answer: answer = 4
4 Correct 1 ms 384 KB Correct answer: answer = 12
5 Correct 0 ms 384 KB Correct answer: answer = 52
6 Correct 1 ms 384 KB Correct answer: answer = 210
7 Correct 0 ms 384 KB Correct answer: answer = 88
8 Incorrect 1 ms 768 KB Wrong answer: output = 7698, expected = 7696
9 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 384 KB Correct answer: answer = 4
3 Correct 0 ms 384 KB Correct answer: answer = 4
4 Correct 1 ms 384 KB Correct answer: answer = 12
5 Correct 0 ms 384 KB Correct answer: answer = 52
6 Correct 1 ms 384 KB Correct answer: answer = 210
7 Correct 0 ms 384 KB Correct answer: answer = 88
8 Incorrect 1 ms 768 KB Wrong answer: output = 7698, expected = 7696
9 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 384 KB Correct answer: answer = 4
3 Correct 0 ms 384 KB Correct answer: answer = 4
4 Correct 1 ms 384 KB Correct answer: answer = 12
5 Correct 0 ms 384 KB Correct answer: answer = 52
6 Correct 1 ms 384 KB Correct answer: answer = 210
7 Correct 0 ms 384 KB Correct answer: answer = 88
8 Incorrect 1 ms 768 KB Wrong answer: output = 7698, expected = 7696
9 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct answer: answer = 4
2 Correct 0 ms 384 KB Correct answer: answer = 4
3 Correct 0 ms 384 KB Correct answer: answer = 4
4 Correct 1 ms 384 KB Correct answer: answer = 12
5 Correct 0 ms 384 KB Correct answer: answer = 52
6 Correct 1 ms 384 KB Correct answer: answer = 210
7 Correct 0 ms 384 KB Correct answer: answer = 88
8 Incorrect 1 ms 768 KB Wrong answer: output = 7698, expected = 7696
9 Halted 0 ms 0 KB -