Submission #601125

#	Time	Username	Problem	Language	Result	Execution time	Memory
601125		MohamedAliSaidane	Aliens (IOI16_aliens)	C++14	12 / 100	132 ms	2260 KiB

aliens

#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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40