Submission #1175216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175216		HappyCapybara	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	328 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

vector<int> lg;
vector<vector<int>> st;

int query(int l, int r){
    int d = 31-__builtin_clz(r-l+1);
    //cout << l << " " << r << " " << d << endl;
    //cout << st[d][l] << endl;
    return min(st[d][l], st[d][r-(1<<d)+1]);
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    int lp = -1;
    st.resize(20, vector<int>(m, m));
    for (int i=0; i<n; i++){
        st[0][max(r[i], c[i])] = min(st[0][max(r[i], c[i])], min(r[i], c[i]));
        lp = max(lp, max(r[i], c[i]));
    }
    //for (int i=0; i<m; i++) cout << st[0][i] << " ";
    //cout << endl << lp << endl;
    for (int j=1; j<20; j++){
        for (int i=0; i<m; i++){
            if (i+1<<(j-1)-1 >= m) continue;
            st[j][i] = min(st[j-1][i], st[j-1][i+1<<(j-1)]);
        }
    }
    lg.resize(m);
    vector<vector<ll>> dp(m+1, vector<ll>(k+1, 1ll<<50));
    for (int i=0; i<=k; i++) dp[m][i] = 0;
    for (int i=lp+1; i<=m; i++) dp[i][0] = 0;
    //cout << query(3, 6) << " a\n";
    for (int kl=1; kl<=k; kl++){
        for (int i=m-1; i>=0; i--){
            for (int j=i+1; j<=m; j++){
                ll d = query(i, j-1);
                ll cost = 0;
                if (d != m){
                    cost = pow((j-d), 2)-pow(max(i-d, 0ll), 2);
                }
                //cout << i << " " << j << " " << d << " " << cost << endl;
                dp[i][kl] = min(dp[i][kl], cost+dp[j][kl-1]);
            }
            //cout << i << " " << kl << " " << dp[i][kl] << endl;
        }
    }
    return dp[0][k];
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40