oj.uz

Submission #601125

# Submission time Handle Problem Language Result Execution time Memory
601125 2022-07-21T11:46:09 Z MohamedAliSaidane Aliens (IOI16_aliens) C++14
12 / 100
 132 ms 2260 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "aliens.h"

        using namespace std;
        using namespace __gnu_pbds;


        ///#define int long long

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define ff first
        #define ss second

        #define pb push_back
        #define popb pop_back
        #define all(x) (x).begin(),(x).end()

        const ll INF = 1e18;
        ll take_photos(int n, int m, int k, vi r, vi c)
        {
            sort(all(r));
             ll dp[n + 1][k + 1];
             for(int i = n; i >= 0; i --)
                for(int j=  k - 1; j>= 0; j--)
                    dp[i][j] = INF;
             for(int j=  k - 1; j >= 0; j--)
                dp[n][j] = 0ll;
             for(int i= n - 1; i >= 0; i--)
             {
                 for(int j= k - 1; j >= 0; j --)
                 {
                     if(i == n- 1)
                     {
                        dp[i][j] = 1ll;
                        continue;
                     }
                     if(j == 0)
                     {
                         dp[i][j] = (r[n - 1] - r[i] + 1ll) * 1ll * (r[n - 1] - r[i] + 1ll);
                         continue;
                     }
                     for(int l = n - 1; l >= i; l --)
                     {
                         dp[i][j] = min(dp[i][j], dp[l + 1][j - 1] + (r[l] - r[i] + 1ll) *1ll* ( r[l] - r[i]+ 1ll));
                     }
                 }
             }
             return dp[0][k - 1];
        }

Subtask #1
0 / 4.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Correct answer: answer = 1
2 Correct 1 ms 212 KB Correct answer: answer = 4
3 Correct 0 ms 212 KB Correct answer: answer = 1
4 Correct 0 ms 212 KB Correct answer: answer = 5
5 Correct 0 ms 212 KB Correct answer: answer = 41
6 Correct 0 ms 304 KB Correct answer: answer = 71923
7 Correct 1 ms 212 KB Correct answer: answer = 77137
8 Correct 65 ms 1268 KB Correct answer: answer = 764
9 Correct 1 ms 212 KB Correct answer: answer = 250000
10 Correct 131 ms 2260 KB Correct answer: answer = 500
11 Correct 0 ms 212 KB Correct answer: answer = 32
12 Correct 1 ms 212 KB Correct answer: answer = 130050
13 Correct 12 ms 496 KB Correct answer: answer = 5110
14 Correct 2 ms 300 KB Correct answer: answer = 2626
15 Correct 6 ms 520 KB Correct answer: answer = 796
16 Correct 8 ms 340 KB Correct answer: answer = 7580
17 Correct 31 ms 724 KB Correct answer: answer = 1904
18 Correct 1 ms 212 KB Correct answer: answer = 996004
19 Correct 6 ms 340 KB Correct answer: answer = 38817
20 Correct 23 ms 680 KB Correct answer: answer = 4096
21 Correct 1 ms 340 KB Correct answer: answer = 1
22 Correct 130 ms 2260 KB Correct answer: answer = 1
23 Correct 29 ms 724 KB Correct answer: answer = 2040
24 Correct 132 ms 2260 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 212 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 212 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 212 KB Wrong answer: output = 1, expected = 4
2 Halted 0 ms 0 KB -